Как рифмовать? Как играть в шахматы? Как побеждать врагов? Как водружать флаги?
Вы хотите написать текст песни, состоящий из $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$ |