問題文

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$ で割った余りを出力してください。 最後に改行してください。

サンプル

3 1

4

10 53

268129654

50 100

429346442