Jak rymować? Jak grać w szachy? Jak pokonać wroga? Jak zatknąć flagę?
Chcesz napisać tekst piosenki składający się z $nd$ znaków. Zaprojektowałeś $k$ rodzajów rymów, a każdy znak musi pasować do dokładnie jednego rodzaju rymu. Piosenka brzmi dobrze tylko wtedy, gdy liczba wystąpień każdego rodzaju rymu w tekście jest wielokrotnością $d$. Ile istnieje sposobów przypisania rymów, aby piosenka brzmiała dobrze? Odpowiedź podaj modulo $1049874433$.
Wejście
Pierwsza linia zawiera trzy liczby całkowite $n, k, d$, zgodnie z treścią zadania.
Wyjście
Jedna linia zawierająca jedną liczbę całkowitą, będącą wynikiem.
Przykład
Przykład 1
2 2 2
Wyjście 1
8
Przykład 2
2 3 4
Wyjście 2
213
Przykład 3
2 4 6
Wyjście 3
5548
Ograniczenia
Dla $100\%$ danych wejściowych: $0\le n\le 10^9, 1\le k\le 2000, d \in \{1, 2, 3, 4, 6\}$.
| Numer testu | $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$ |