Competitions

# Exponentiation

# Just Add It

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

(`Z`

+ _{n}`Z`

- 2_{n-1}`Z`

) mod _{n-2}**10000007**,

where `Z`

= _{n}`S`

+ _{n}`P`

and _{n}`S`

= _{n}`1`

+ ^{k}`2`

+ ^{k}`3`

+ ... + ^{k}`n`

and ^{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*`10`

, ^{8}**0** < **k** < `10`

). The last line contains two zeros and should not be processed.^{6}

#### Output

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

Input example #1

10 3 9 31 83 17 5 2 0 0

Output example #1

4835897 2118762 2285275 3694