P5364 [SNOI2017] Gifts

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

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

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

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