AMAZMOSQ

The mosquitoes of the Amazon are less famous than those of the West Nile. Perhaps because they only live for one day. However, they multiply very quickly. We start with ~S~ mosquitoes on day ~0~. During a day, each mosquito bites one person. Then, it gives birth to ~K~ new mosquitoes and immediately dies.

Find out how many bites the human race will have received in total, at the end of the ~N~-th day.

The number of bites will be very large, so you are asked to find the remainder of its division by ~20.140.409~.

Input

The input will consist of a single line containing three natural numbers, ~S~, ~K~, ~N~, separated in pairs by a single space.

Output

The output should consist of a single line containing one natural number: the remainder of the division of the total number of bites by ~20.140.409~.

Constraints

~1 \le S \le 1.000~
~1 \le K \le 100~
~0 \le N \le 50.000.000~
Execution time limit: 1 sec.
Memory limit: 64 MB.

Examples of Input - Output

1st

STDIN (amazmosq.in)

1 2 12

STDOUT (amazmosq.out)

8191

2nd

STDIN (amazmosq.in)

3 42 5

STDOUT (amazmosq.out)

18968698

Explanation of the Examples: The evolution of mosquitoes and bites for the two examples: