Competitions

# Exponentiation

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. Each case is a separate line that contains two positive integers n and k (1 < n < 2*108, 0 < k < 106). The last line contains two zeros and should not be processed.

#### Output

For each test case print the required 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