韻要怎麼押？棋要怎麼下？敵要怎麼殺？旗要怎麼插？
現在你想要寫一首歌詞，一共有 $nd$ 個字，你一共設計了 $k$ 種韻腳，每個字恰好要符合一種韻腳。並且只有當每種韻腳在歌詞中出現的字數恰為 $d$ 的倍數時，這首歌才好聽。試問一共有多少種韻腳的搭配方法，使得歌詞好聽？你只需要回答方案數對於 $1049874433$ 取模的結果即可。
輸入格式
第一行三個整數 $n, k, d$，如題意所示。
輸出格式
一行一個整數，表示答案。
範例
範例輸入 1
2 2 2範例輸出 1
8範例輸入 2
2 3 4範例輸出 2
213範例輸入 3
2 4 6範例輸出 3
5548資料範圍
對於 $100\%$ 的資料，保證 $0\le n\le 10^9, 1\le k\le 2000, d \in \{1, 2, 3, 4, 6\}$。
| 測試點編號 | $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$ |