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}$
| Test Case | $n$ | $k$ | $d$ |
|---|---|---|---|
| $1$ | $\le 5\times 10^4$ | $\le 2\times 10^3$ | $2$ |
| $2$ | $3$ | ||
| $3$ | $4$ | ||
| $4$ | $6$ | ||
| $5$ | $\le 10^9$ | $1$ | |
| $6$ | |||
| $7$ | $2$ | ||
| $8$ | |||
| $9$ | $3$ | ||
| $10$ | |||
| $11$ | $\le 10^3$ | $4$ | |
| $12$ | |||
| $13$ | $\le 2\times 10^3$ | ||
| $14$ | |||
| $15$ | $\le 10^3$ | $6$ | |
| $16$ | |||
| $17$ | |||
| $18$ | |||
| $19$ | $\le 2\times 10^3$ | ||
| $20$ |