ZSUM  Just Add It
For two given integers n and k find (Z_{n} + Z_{n1}  2Z_{n2}) mod 10000007, where Z_{n} = S_{n} + P_{n} and S_{n} = 1^{k} + 2^{k} + 3^{k} + … + n^{k} and P_{n} = 1^{1} + 2^{2} + 3^{3} + … + n^{n}.
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
amalik123:
20170322 11:08:55
modular exponentiation is the key,easy one


nilabja16180:
20170321 17:24:52
Modular Exponentiation don't overthink! 

rohit9934:
20170309 18:45:21
Dont think too much,its easy.Just write one function for calculating mod.and then just write that Algebraic Expression in form of one function as a variable.Thats it.AC in 1 go after a long time.(After 1st prob :D) 0.01 sec in C. 

nishanth2066:
20170123 15:00:18
TLE in .py AC in C


kass_97:
20170114 10:34:57
No way to get past TLE unless you use modular exponentiation 

apurvgs:
20161224 13:18:32
modular exponentiation


rohit_2407:
20161215 12:15:28
learned a new concept !!


venky1001:
20161210 10:28:42
TLE in JAVA :/


azelf:
20161105 19:34:35
TLE with java with correct logic


surajmall:
20161004 16:17:48
its some what tricky but but biginners must try it

Added by:  Manohar Singh 
Date:  20110904 
Time limit:  0.180s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Manohar Singh 