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
md_yasin:
20200522 10:39:16
AC in one go!!! :v be careful to use long long and calculate power 

deependra_18:
20200412 14:10:25
thanks @sicklesplit for pointing 1e7+7 is not a prime . 

izrail:
20200409 17:18:45
n^k+2(n1)^k+2(n1)^(n1)+n^n careful about mod and evaluate this exp. 

subodh898:
20191028 13:44:01
just solve the final relation given in terms of n and use binary exponentiation. Also careful about the mod, it is 1e7+7. 

destiny_gamer:
20191001 13:54:45
AC in one go! Finaally! 

a_l_o_n_e:
20190829 16:27:05
AC in one go!!! 

sicklesplit:
20190822 16:02:19
Reemember that 1e7+7 is not prime. 

sea_26:
20190729 20:07:02
AC in one go with 0.01 Sec


shreyash1999:
20190701 14:05:26
i m getting all answers correct except 10 3 it is comming negative value in have taken long long also


mubasshir00:
20190522 21:48:34
Just Use Binary Exponentiation and Sum of N number formula :p then GET AC and thanks me 
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 