ZSUM - Just Add It
For two given integers n and k find (Zn + Zn-1 - 2Zn-2) mod 10000007, where Zn = Sn + Pn and Sn = 1k + 2k + 3k + … + nk and Pn = 11 + 22 + 33 + … + nn.
Input
There are several test cases (≤ 10000). In each case two space separated positive integers n and k are given.
For last test case n and k are given as 0 0, which is not to be processed.
Constraints
1 < n < 200000000 0 < k < 1000000
Output
For each case print the asked value in separate line.
Example
Input: 10 3 9 31 83 17 5 2 0 0 Output: 4835897 2118762 2285275 3694
hide comments
divine_himani:
2015-06-11 18:11:07
Python coders please do not attempt the problem, it will be a total waste of time as will always get a TLE |
|
Aman Agarwal:
2015-06-06 09:16:04
Modular exponentiation would help
|
|
THECOLDONE:
2015-05-27 20:57:00
thanks @ deadbrain
|
|
deadbrain:
2015-01-27 14:55:09
for those who don't know how to solve the problem efficiently, read Modular exponentiation wiki article first... Lot to learn from this question. |
|
sarelfeniel:
2014-05-03 09:28:40
Great problem.
|
Added by: | Manohar Singh |
Date: | 2011-09-04 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | Manohar Singh |