e-olymp
Competitions

Power + Euler function

Just Add It

For two given integers n and k find

(Zn + Zn-1 - 2Zn-2) mod 10000007,

where Zn = Sn + Pn and Sn = 1k + 2k + 3k + ... + nk and Pn = 11 + 22 + 33 + ... + nn.

Input

There are several test cases. In each case two space separated positive integers n and k (1 < n < 2*108, 0 < k < 106) are given. The last test case contains two zeros and will not be processed.

Output

For each test case print the found value in a separate line.

Time limit 1 second
Memory limit 122.17 MiB
Input example #1
10 3
9 31
83 17
5 2
0 0
Output example #1
4835897
2118762
2285275
3694