韻をどう踏むか？ 棋をどう打つか？ 敵をどう殺すか？ 旗をどう立てるか？
今、あなたは歌詞を書こうとしており、全体で $nd$ 文字あります。あなたは $k$ 種類の韻脚を設計し、各文字はちょうど1つの韻脚に適合しなければなりません。すべての韻脚が歌詞の中で出現する回数がちょうど $d$ の倍数であるときのみ、その歌は「心地よい」ものとなります。歌詞が心地よいものとなるような韻脚の組み合わせは何通りあるでしょうか？ 答えを $1049874433$ で割った余りを求めてください。
入力
1行目に3つの整数 $n, k, d$ が与えられます。
出力
答えを1行で出力してください。
入出力例
入力 1
2 2 2出力 1
8入力 2
2 3 4出力 2
213入力 3
2 4 6出力 3
5548制約
すべてのデータにおいて、$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$ |