Just Add It

Very easy

Execution time limit is 1 second

Runtime memory usage limit is 128 megabytes

For two given integers $n$ and $k$ find

(Z_{n} + Z_{n - 1} - 2 \cdot Z_{n - 2}) m o d 10000007,

where

Z_{n} = S_{n} + P_{n},

S_{n} = 1^{k} + 2^{k} + 3^{k} + ... + n^{k},

P_{n} = 1^{1} + 2^{2} + 3^{3} + ... + n^{n}

Input

There are several test cases. Each case is a separate line that contains two positive integers $n$ and $k (1 < n < 2 \cdot 1 0^{8}, 0 < k < 1 0^{6})$ . The last line contains two zeros and should not be processed.

Output

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

Examples

Input #1

Answer #1

Submissions 1K

Acceptance rate 43%