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
azelf:
20161105 19:34:35
TLE with java with correct logic


surajmall:
20161004 16:17:48
its some what tricky but but biginners must try it


Abhishek:
20160924 19:04:10
please increase time limit for python, or remove it from the available languages 

marshmellow:
20160831 14:40:54
dont get nervous by looking at the description of question... Its very easy when you simplify the equation.


sy_117:
20160816 14:47:58
Easy one if u do a little bit of pen paper work !!! mod=10^7+7.......... 

avidcoder:
20160716 07:53:08
Last edit: 20160716 07:54:26 

vineetpratik:
20160705 16:29:50
Simplification.modular exponentiation AC in 0.02 , 1st go :) 

ragwave:
20160511 17:28:20
visit this link for refrence


Neeraj Joshi:
20160322 17:50:41
50th... 

pt97:
20160308 15:29:49
use fu*king mod every where

Added by:  Manohar Singh 
Date:  20110904 
Time limit:  0.180s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 
Resource:  Manohar Singh 