For two given integers n and k find (Z_n + Z_n-1 - 2Z_n-2) mod 10000007, where Z_n = S_n + P_n and S_n = 1^k + 2^k + 3^k + … + n^k and P_n = 1¹ + 2² + 3³ + … + 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