好的，我已按照你的要求对题目进行了重新排版，在数字和公式前后添加了 $ 符号。以下是修改后的版本：

---

题目描述

热情好客的🐒请森林中的朋友们吃饭，他的朋友被编号为 $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 1000000007$。

---

输入格式

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

---

输出格式

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

---

样例 1

输入

4 2

输出

37

---

样例 2

输入

2333333 2

输出

514898185

---

样例 3

输入

1234567890000 3

输出

891659731

---

样例 4

输入

66666666 10

输出

32306309

---

数据范围与提示

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

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

---