1343: #2253. 「SNOI2017」礼物

Memory Limit:512 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

热情好客的小猴请森林中的朋友们吃饭,他的朋友被编号为 1∼N1\sim N1N,每个到来的朋友都会带给他一些礼物:香蕉。其中,第一个朋友会带给他 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^6N106
另外 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}N1018K≤10K\leq 10K10

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