Description

The hospitable little monkey invites friends from the forest to dinner. His friends are numbered from $1$ to $n$. Each friend who arrives brings him some gifts: big bananas. The first friend brings him $1$ big banana. After that, when each friend arrives, they will bring the total number of gifts brought by all previous friends, plus their index raised to the $k$-th power.

So, if $k=2$, the number of gifts brought by the first few friends is:

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

If $k=3$, the number of gifts brought by the first few friends is:

$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 you for help.

Given $n,k$, output the number of gifts brought by the $n$-th friend $\bmod \ 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 $\bmod \ 10^9+7$.

4 2

37

2333333 2

514898185

1234567890000 3

891659731

1000000013 10

616417347

Hint

$\text{10}\%$ of the testdata: $n \le 10^6$.

Another $\text{10}\%$ of the testdata: $k \le 3$.

The first $\text{40}\%$ of the testdata: $n \le 10^{18}, k \le 10$.

The first $\text{60}\%$ of the testdata: $n \le 10^{18}, k \le 1000$.

The first $\text{70}\%$ of the testdata: $k \le 1000$.

The first $\text{90}\%$ of the testdata: $k \le 10^6$.

$\text{100}\%$ of the testdata: $n\le 10^{100000},k \le 2\times10^7$.

The time limit for the last test point is $2s$, and for the others it is $1s$.

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

Translated by ChatGPT 5