Now, you want to write a song lyric consisting of exactly $nd$ characters. You have designed $k$ different types of rhyme endings, and each character must conform to exactly one rhyme ending. Moreover, the song only sounds pleasant if and only if, for every rhyme type, the number of characters matching that rhyme is a multiple of $d$.

How many different rhyme-type assignments make the song pleasant? You only need to output the result modulo $1049874433$.

Input Format

The first line contains three integers $n$, $k$, and $d$, as described above.

Output Format

Output a single integer — the number of valid rhyme-type assignments modulo $1049874433$.

Sample Input 1

2 2 2

Sample Output 1

8

Sample Input 2

2 3 4

Sample Output 2

213

Sample Input 3

2 4 6

Sample Output 3

5548

Constraints

For 100% of the data, the following holds:

• $0 \le n \le 10^9$
• $1 \le k \le 2000$
• $d \in {1, 2, 3, 4, 6}$