B. Sequences
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Let's consider the sequences of $$$n$$$ symbols. Let's say the sequence is $$$k$$$-simple if the symbols at positions $$$i$$$ and $$$i+k$$$ ($$$1 \leq i \leq n - k$$$) are different. Determine the number of $$$k$$$-simple sequences consisting of the first $$$m$$$ Latin letters.

Input

The first line has three integer numbers n ($$$1 \leq n \leq 40$$$), m ($$$1 \leq m \leq 8$$$) and k ($$$1 \leq k \leq 8$$$).

Output

Output one integer equal to the number of such sequences.

Example
Input
3 2 2
Output
4
Note

In the example the sequences are: aab, abb, baa, bba.