Problem Background

How should rhymes be arranged? How should the game be played? How should the enemy be defeated? How should the flag be planted?

Problem Description

You want to write a song with a total of $nd$ characters. You have designed $k$ different rhyme schemes, and each character must fit exactly one of these rhyme schemes.

The song sounds good only if the number of characters for each rhyme scheme is exactly a multiple of $d$.

How many ways are there to arrange the rhyme schemes to make the song sound good?

You only need to answer the number of ways modulo $1049874433$.

Input Format

A single line containing three integers $n, k, d$ as described in the problem.

Output Format

A single line containing an integer, representing the answer.

Sample Input and Output

Sample Input #1

2 2 2

Sample Output #1

8

Sample Input #2

2 3 4

Sample Output #2

213

Sample Input #3

2 4 6

Sample Output #3

5548

Notes

For $100\%$ of the data, it is guaranteed that:
$0 \le n \le 10^9$
$1 \le k \le 2000$
$d \in \{1, 2, 3, 4, 6\}$

By: EntropyIncreaser

见题面 Input 部分

见题面 Output 部分