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.
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
Added by:  Manohar Singh 
Date:  20110904 
Time limit:  0.180s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel Pentium G860 3GHz) 
Languages:  All except: SCM chicken 
Resource:  Manohar Singh 
hide comments
Arpit Gupta:
20150629 11:16:47
Modular exponentiation'll help a lot...:) Last edit: 20150629 11:17:04 

Sejal Vaghela:
20150620 18:32:23
Thanks @ deadbrain


divine_himani:
20150611 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:
20150606 09:16:04
Modular exponentiation would help


THECOLDONE:
20150527 20:57:00
thanks @ deadbrain


deadbrain:
20150127 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:
20140503 09:28:40
Great problem.
