問題文

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

サンプル

3 1

4

2 2

11

5 10

334032363