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
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 :) 

coolboy7:
20200726 19:41:33
@ashish try to solve the expression first you will see that some terms will be cancelling 

coolboy7:
20200726 19:26:17
it's binary exponentiation


ks_r:
20200723 13:08:28
AC In One GO !! :) 

ashish_2495:
20200608 18:05:05
I am using binary exponention and got sample results but the spoj shows tle...


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