Problem Statement

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

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

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 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

$M\ K$

$M,K$ are integers.
$1 \leq M \leq 50$
$1 \leq K \leq 10^9$

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

10 53

268129654

50 100

429346442