No.1049 Zero (Exhaust)

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 173
作問者 : stoqstoq / テスター : tran0826tran0826
26 ProblemId : 4094 / 出題時の順位表
問題文最終更新日: 2020-05-30 02:17:19

問題文

Oくんは整数 $N$ を持っています。はじめ、$N=0$ です。
Oくんは次の操作(1)、(2)のいずれか一方を毎回選び、行います。これを $K$ 回繰り返します。ここで、 $P$ は素数です。

(1)整数 $i \ (0 \leq i \leq P-1)$ を1つ選ぶ。その後 $N$ を、$N+i$ を $P$ で割った余りで置き換える。
(2)整数 $i \ (0 \leq i \leq P-1)$ を1つ選ぶ。その後 $N$ を、$N \times i$ を $P$ で割った余りで置き換える。

$K$ 回の操作後に、再び $N=0$ となるような操作列は何通りあるでしょうか?そのような操作列の総数を $10^9+7$ で割った余りを求めてください。
ただし2つの操作列が異なるとは、ある $i \ (1 \leq i \leq K)$ が存在して、$i$ 番目の操作が異なる ((1)か(2)かが異なる、または足した/掛けた値が異なる)ことを表します。

入力

$P\ K$

$P$ は素数
$K$ は整数
$1 \leq P \leq 10^9$
$1 \leq K \leq 10^6$

出力

条件を満たす操作列の個数を $10^9+7$ で割った余りを出力してください。 最後に改行してください。

サンプル

サンプル1
入力
3 1
出力
4

条件を満たす操作(列)は次の4通りです。
・0を足す。
・0を掛ける。
・1を掛ける。
・2を掛ける。

サンプル2
入力
2 2
出力
11

サンプル3
入力
5 10
出力
334032363

$10^9+7$ で割った余りを出力することに注意してください。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。