1401: 「SNOI2017」礼物
[Creator : ]
Description
热情好客的
请森林中的朋友们吃饭，他的朋友被编号为 1∼N1\sim N1∼N，每个到来的朋友都会带给他一些礼物：
。其中，第一个朋友会带给他 111 个，之后，每一个朋友到来以后，都会带给他之前所有人带来的礼物个数再加他的编号的 KKK 次方那么多个。所以，假设 K=2K=2K=2，前几位朋友带来的礼物个数分别是：
1,5,15,37,83,…1,5,15,37,83,\ldots1,5,15,37,83,…
假设 K=3K=3K=3，前几位朋友带来的礼物个数分别是：
1,9,37,111,…1,9,37,111,\ldots1,9,37,111,…
现在，好奇自己到底能收到第 NNN 个朋友多少礼物，因此拜托于你了。
已知 N,KN,KN,K，请输出第 NNN 个朋友送的礼物个数 mod1000000007。
输入格式
第一行，两个整数 N,KN,KN,K。
输出格式
一个整数，表示第 NNN 个朋友送的礼物个数 mod1000000007。
样例
样例输入 1
4 2
样例输出 1
37
样例输入 2
2333333 2
样例输出 2
514898185
样例输入 3
1234567890000 3
样例输出 3
891659731
样例输入 4
66666666 10
样例输出 4
32306309
数据范围与提示
20%20\%20% 的数据：N≤106N\leq 10^6N≤106。
另外 10%10\%10% 的数据：K=1K=1K=1。
另外 20%20\%20% 的数据：K=2K=2K=2。
另外 20%20\%20% 的数据：K=3K=3K=3。
100%100\%100% 的数据：N≤1018N\leq 10^{18}N≤1018，K≤10K\leq 10K≤10。
数据范围与原题相同，但测试数据由本站会员自制，并非原数据。
时限已按照评测机速度调整，原题时限为 2000ms。