[SNOI2017]礼物

题目描述

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

输入输出格式

输入格式


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

输出格式


一个整数,表示第 $N$ 个朋友送的礼物个数对 $10^9+7$ 取模的结果。

输入输出样例

输入样例 #1

4 2

输出样例 #1

37

输入样例 #2

2333333 2

输出样例 #2

514898185

输入样例 #3

1234567890000 3

输出样例 #3

891659731

输入样例 #4

66666666 10

输出样例 #4

32306309

说明

- $20\%$ 的数据:$N \le 10^6$; - 另外 $10\%$ 的数据:$K=1$; - 另外 $20\%$ 的数据:$K=2$; - 另外 $20\%$ 的数据:$K=3$; - $100\%$ 的数据:$N \le 10^{18}$,$K \le 10$。