Description

The hospitable little monkey invites friends from the forest to dinner. His friends are numbered from $1$ to $N$. Each arriving friend will bring him some gifts: big bananas.

The first friend brings $1$ big banana. After that, when each friend arrives, they will bring the total number of gifts brought by all previous friends, plus their own index raised to the $K$-th power.

So, if $K=2$, the numbers of gifts brought by the first few friends are:

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

If $K=3$, the numbers of gifts brought by the first few friends are:

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

Now, the little monkey is curious about how many gifts he will receive from the $N$-th friend, so he asks for your help.

Given $N$ and $K$, output the number of gifts brought by the $N$-th friend modulo $10^9+7$.

Input Format

The first line contains two integers $N,K$.

Output Format

Output one integer, representing the number of gifts brought by the $N$-th friend modulo $10^9+7$.

4 2

37

2333333 2

514898185

1234567890000 3

891659731

66666666 10

32306309

Hint

• $20\%$ of the testdata: $N \le 10^6$.
• Another $10\%$ of the testdata: $K=1$.
• Another $20\%$ of the testdata: $K=2$.
• Another $20\%$ of the testdata: $K=3$.
• $100\%$ of the testdata: $N \le 10^{18}$, $K \le 10$.

Translated by ChatGPT 5