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
mishkat007:
20220915 15:52:47
Is the equation correct after solving??


taejin_101:
20220804 16:26:41
Hence proved never get afraid just by looking at a question...


wraith_11:
20211123 20:13:54
very easy, just remember mod = 1e7 + 7, and simply try to reduce the equation by +,  and at the end, use binary exponentiation 

samrat2825:
20211115 16:51:02
Use 10^7 + 7 and not 10^9+7 

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? 
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 