[SNOI2017] 礼物 加强版

原题链接 [P5364](https://www.luogu.org/problemnew/show/P5364)

热情好客的**小猴子**请森林中的朋友们吃饭，他的朋友被编号为 $1\sim n$，每个到来的朋友都会带给他一些礼物：**大香蕉**。其中，第一个朋友会带给他 $1$ 个**大香蕉**，之后，每一个朋友到来以后，都会带给他之前所有人带来的礼物个数再加他的编号的 $k$ 次方那么多个。所以，假设 $k=2$，前几位朋友带来的礼物个数分别是： $1,5,15,37,83,\ldots$ 假设 $k=3$，前几位朋友带来的礼物个数分别是： $1,9,37,111,\ldots$ 现在，**小猴子**好奇自己到底能收到第 $n$ 个朋友多少礼物，因此拜托于你了。 已知 $n,k$，请输出第 $n$ 个朋友送的礼物个数 $\bmod \ 10^9+7$。

第一行，两个整数 $n,k$。

一个整数，表示第 $n$ 个朋友送的礼物个数 $\bmod \ 10^9+7$。

4 2

37

2333333 2

514898185

1234567890000 3

891659731

1000000013 10

616417347

$\text{10}\%$ 的数据：$n \le 10^6$。 另外 $\text{10}\%$ 的数据：$k \le 3$。 前 $\text{40}\%$ 的数据：$n \le 10^{18}, k \le 10$。 前 $\text{60}\%$ 的数据：$n \le 10^{18}, k \le 1000$。 前 $\text{70}\%$ 的数据：$k \le 1000$。 前 $\text{90}\%$ 的数据：$k \le 10^6$。 $\text{100}\%$ 的数据：$n\le 10^{100000},k \le 2\times10^7$。 最后一个测试点的时限为 $2s$，其余为 $1s$。 **** NaCly\_Fish：本题原数据有误，现已修复。