P5548 [BJ United Round #3] Rhyming.

How do you rhyme? How do you play chess? How do you kill enemies? How do you plant the flag?

Now you want to write a song lyric with a total of $nd$ characters. You have designed $k$ types of rhyme endings, and each character must fit exactly one type of rhyme ending. Also, the song sounds good only if, for every rhyme ending type, the number of characters in the lyric that use this rhyme ending is exactly a multiple of $d$. How many ways are there to assign rhyme endings so that the song sounds good? You only need to output the number of ways modulo $1049874433$.

One line with three integers $n,k,d$, as described.

One line with one integer, the answer.

For $100\%$ of the testdata, it is guaranteed that: $0 \le n \le 10^9$ $1 \le k \le 2000$ $d \in \{ 1,2,3,4,6 \}$ By: EntropyIncreaser Translated by ChatGPT 5