2488: #2253. 「SNOI2017」礼物

热情好客的请森林中的朋友们吃饭，他的朋友被编号为 $1\sim N$，每个到来的朋友都会带给他一些礼物：。其中，第一个朋友会带给他 $1$ 个，之后，每一个朋友到来以后，都会带给他之前所有人带来的礼物个数再加他的编号的 $K$ 次方那么多个。所以，假设 $K=2$，前几位朋友带来的礼物个数分别是：

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

假设 $K=3$，前几位朋友带来的礼物个数分别是：

$1,9,37,111,\dots$

现在，好奇自己到底能收到第 $N$ 个朋友多少礼物，因此拜托于你了。

已知 $N,K$，请输出第 $N$ 个朋友送的礼物个数 $mod1000000007$。

输入格式

第一行，两个整数 $N,K$。

输出格式

一个整数，表示第 $N$ 个朋友送的礼物个数 $mod1000000007$。

样例

样例输入 1

4 2

样例输出 1

37

样例输入 2

2333333 2

样例输出 2

514898185

样例输入 3

1234567890000 3

样例输出 3

891659731

样例输入 4

66666666 10

样例输出 4

32306309

数据范围与提示

$20\%$ 的数据：N≤106N\leq 10^6N≤10​6​​。
另外 $10\%$ 的数据：$K=1$。
另外 $20\%$ 的数据：$K=2$。
另外 $20\%$ 的数据：$K=3$。
$100\%$ 的数据：N≤1018N\leq 10^{18}N≤10​18​​，$K\le 10$。

数据范围与原题相同，但测试数据由本站会员自制，并非原数据。
时限已按照评测机速度调整，原题时限为 $2000\text{ms}$。