Problem Statement

O-kun has an integer $N$. Initially, $N=0$.
Each time, O-kun chooses one of the following operations (1) and (2) and performs it. He repeats this $K$ times. Here, $P$ is a prime number.

(1) Choose one integer $i \ (0 \leq i \leq P-1)$. Then replace $N$ with the remainder of $N+i$ divided by $P$.
(2) Choose one integer $i \ (0 \leq i \leq P-1)$. Then replace $N$ with the remainder of $N \times i$ divided by $P$.

How many sequences of operations result in $N=0$ again after the $K$ operations? Find the total number of such sequences of operations, modulo $10^9+7$.
Here, two sequences of operations are considered different if there exists some $i \ (1 \leq i \leq K)$ such that the $i$-th operations differ (that is, they differ in whether (1) or (2) is used, or in the value added/multiplied).

Input

$P\ K$

$P$ is a prime number
$K$ is an integer
$1 \leq P \leq 10^9$
$1 \leq K \leq 10^6$

Output

Output the number of sequences of operations satisfying the condition, modulo $10^9+7$. Print a newline at the end.

Sample

3 1

4

2 2

11

5 10

334032363