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
hide comments
farhan764:
20160131 16:15:55
modular exponentiation.......use wiki and math world 

lakshay_v06:
20160125 12:22:42
After simplifying the equation, you will have to use Modular exponentiation... :) > MY 88th. Last edit: 20160125 12:24:26 

darkhire21:
20151224 06:44:52
In first go ...!!!


Vipul Srivastava:
20151208 09:54:39
Same code gives TLE in Python 

dragonemperor:
20151021 07:52:48
AC at first go. Needed some time to reduce the equation though :) 

MishThi:
20151001 07:15:36
Python :( TLE Last edit: 20151001 07:15:49 

Ravi Chandra:
20150915 07:29:01
Hey my 54th 

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 :) 
Added by:  Manohar Singh 
Date:  20110904 
Time limit:  0.180s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 
Resource:  Manohar Singh 