407234: GYM102700 D Dice

D. Dicetime limit per test6 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

Diego has bought $$$n$$$ dices to play with, all dices have $$$k$$$ sides numbered $$$1,2,...,k$$$, also as Diego wants to trick his friends, all dices are loaded, meaning that the probability of rolling the dice is not the same for all sides.

In particular, Diego loaded the dice so that all sides which are multiple of $$$m$$$ have zero probability of appearance, while all other sides have the equal probability of appearance. Diego thinks that this will be enough to win any game betting against multiples of $$$m$$$. Ivan, a friend of Diego, knows the dices are loaded and he thinks that after summing the values of the dices we can still get a good probability of having a multiple of $$$m$$$.

For example, if Diego has 2 dices with 6 sides loaded, such that multiples of 3 cannot appear, then each dice could roll into 1, 2, 4 or 5 with probability 1/4 each. After throwing both dices Diego has the following possible outcomes for multiples of 3:

• 3 with 1/8 of probability
• 6 with 1/4 of probability
• 9 with 1/8 of probability

Therefore, in this case, there is a chance of 1/2 of having a multiple of 3, even if each dice, individually, has 0 chance of having a multiple of 3.

Help Ivan to calculate the probability of having a multiple of $$$m$$$ after summing the result of rolling all $$$n$$$ loaded dices.

Input

The input consists of 3 integers $$$n$$$ ($$$1 \leq n \leq 2*10^6$$$), $$$k$$$ ($$$2 \leq k \leq 2*10^6$$$) and $$$m$$$ ($$$2 \leq m \leq 200$$$) — The number of dices, the number of sides in each dice and the multiple chosen to load the dices, respectively

Output

Let p/q be the probability of having a multiple of $$$m$$$ after rolling the dices. Print just a single integer: $$$p * q^{-1} \mod 1000000007$$$.

ExamplesInput

2 2 2

Output

1

Input

3 2 2

Output

0

Input

2 6 3

Output

500000004