P5364 [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$ 取模的结果。

无

无

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