No.1050 Zero (Maximum)

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

問題文

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

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

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

入力

$M\ K$

$M,K$は整数
$1 \leq M \leq 50$
$1 \leq K \leq 10^9$

出力

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

サンプル

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

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

サンプル2
入力
10 53
出力
268129654

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

サンプル3
入力
50 100
出力
429346442

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