問題文

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

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

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

入力

$PK$

$P$ は素数
$K$ は整数
$1\le P\le {10}^9$
$1\le K\le {10}^6$

出力

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

サンプル

3 1

4

2 2

11

5 10

334032363