P5430 [SNOI2017] Gift (Enhanced Version).

Original problem link: [P5364](https://www.luogu.org/problemnew/show/P5364).

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

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

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

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