Problem Description

The hospitable Little Monkey invites friends from the forest to a meal. His friends are numbered from $1$ to $n$. Each friend brings him some gifts: Big Bananas. The first friend brings him $1$ Big Banana, and each subsequent friend brings the total number of gifts from all previous friends plus his own number raised to the power of $k$. For example, if $k=2$, the number of gifts from the first few friends are:

$1, 5, 15, 37, 83, \ldots$

If $k=3$, the number of gifts from the first few friends are:

$1, 9, 37, 111, \ldots$

Now, Little Monkey is curious about how many gifts he will receive from the $n$-th friend and asks for your help.

Given $n$ and $k$, output the number of gifts the $n$-th friend brings, modulo $10^9 + 7$.

Input Format

The first line contains two integers $n$ and $k$.

Output Format

Output a single integer, the number of gifts the $n$-th friend brings, modulo $10^9 + 7$.

Sample Input and Output

Sample Input #1

4 2

Sample Output #1

37

Sample Input #2

2333333 2

Sample Output #2

514898185

Sample Input #3

1234567890000 3

Sample Output #3

891659731

Sample Input #4

1000000013 10

Sample Output #4

616417347

Notes

• $10\%$ of the data: $n \le 10^6$.
• Another $10\%$ of the data: $k \le 3$.
• The first $40\%$ of the data: $n \le 10^{18}, k \le 10$.
• The first $60\%$ of the data: $n \le 10^{18}, k \le 1000$.
• The first $70\%$ of the data: $k \le 1000$.
• The first $90\%$ of the data: $k \le 10^6$.
• $100\%$ of the data: $n \le 10^{100000}, k \le 2 \times 10^7$.

The time limit for the last test case is $2$ seconds, and $1$ second for the others.

NaCly_Fish: The original data for this problem was incorrect and has been fixed.

见题面 Input 部分

见题面 Output 部分