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 
Resource:  Manohar Singh 
hide comments
pvsmpraveen:
20150829 07:46:30
Got AC, You will definitely learn something from this problem, I spent around 1.5 hour and its worth for it ;) Last edit: 20150829 07:47:01 

prakash_reddy:
20150826 20:39:36
simple question the task is to use effective algo for power of 2 numbers.. :) 

Shivam Singh:
20150822 07:54:00
Interesting question to hit the 75th milestone :) 

ROHIT Kumar:
20150815 19:06:55
watch carefully some terms are cancelling out accepted in one go.....:) Last edit: 20150815 19:22:29 

Mohd Ausaf Jafri:
20150813 19:15:00
use right to left binary exponentiation 

Nilutpal Borgohain:
20150808 15:41:58
simple expansion! kudos! 

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
