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
sadiq252:
20210912 19:05:48
Nice problem!Solved by first try,used binary exponentiation. 

curiousyuvi:
20210528 06:33:53
ac in one go...hint: solve the equation Zn+Zn1 2Zn2....: )


anchord:
20210527 06:13:49
Tbh, this problem was worth of thinking, thanks for this problem, i learned so much from this:3 

srivathsav1410:
20210509 13:43:22
easy one ac in one go just n=5 and k=2 you will get it 

abuhanif:
20210419 17:28:14
@sakshi_38 n is always greater than 1 see constrain 1<n<200000000 

sakshi_38:
20210205 07:58:40
what will be the answer when n=1? 

makdi:
20201201 08:05:39
Be careful , wasted half an hour because it is 10^7 + 7 and not 10^9+7 

aa18:
20201013 18:59:24
Why recursive approach of modular exponentiation is giving WA but iterative got accepted. 

panktishah62:
20200817 11:41:42
Last edit: 20200817 11:42:31 

kishlay1105:
20200726 21:29:22
Just take a pen and paper and solve the above expression , many terms will get cut and you will get a small expression which will be solved using modular exponentiation :) 
Added by:  Manohar Singh 
Date:  20110904 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Manohar Singh 