SPOJ Problem Set (classical)
9494. Just Add It
Problem code: ZSUM

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