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
krish_patel_07:
20240309 04:22:31
I am solving from 30 minitues and i came to know that 1e7+7 is given as modulo.


mradul_2212:
20231105 12:24:40
make sure you have read the question properly. that it is saying when to terminate the program > when you encounter 0 0 stop!!


tejaswini_526:
20231021 11:20:53
can't I use ** in python? Please someone explain me, It says TLE


tr1_ten:
20230623 11:08:09
wtf with mod, i waste so much time with 10^9 + 7 just to realize it is 10^7 + 7 ... 

arq_2002:
20230213 12:12:13
Got it saw the hint where he said use pen and paper lol seems like I am rusty as hell 

starlove54:
20230206 06:41:07
good question Last edit: 20230206 07:22:17 

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