Description

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$.

Input Format

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

Output Format

One line with one integer, the answer.

2 2 2

8

2 3 4

213

2 4 6

5548

Hint

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