There are $k$ distinct repeaters in a group. To celebrate the arrival of Christmas Eve, over the next $n$ seconds, they will choose one excellent repeater to repeat every second. It is quite funny that a repeater only feels happy if the total number of times it has repeated is a multiple of $d$. How many different arrangements are there such that all repeaters feel happy?

Input

A single line containing three positive integers $n$, $k$, and $d$, with meanings as described in the problem statement.

Output

A single line containing a positive integer representing the number of arrangements modulo $19491001$.

Examples

Input 1

4 2 2

Output 1

8

Constraints

This problem uses subtasks for evaluation.

Subtask 1 (5 pts): $d=1$

Subtask 2 (25 pts): $n\leq 1000, k\leq 100$

Subtask 3 (30 pts): $k\leq 500000, d=2$

Subtask 4 (40 pts): $k\leq 1000, d=3$

For all data, $n\leq 10^9, k\leq 500000, d\leq 3$.