Description

现在你想要写一首歌词，一共有 $nd$ 个字，你一共设计了 $k$ 种韵脚，每个字恰好要符合一种韵脚。

并且只有当每种韵脚在歌词中出现的字数恰为 $d$ 的倍数时，这首歌才好听。

试问一共有多少种韵脚的搭配方法，使得歌词好听？

你只需要回答方案数对于 $1049874433$ 取模的结果即可。

Input Format

一行三个整数 $n,k,d$，如题意所示。

Output Format

一行一个整数，表示答案。

2 2 2

8

2 3 4

213

2 4 6

5548

Hint

对于 $100\%$ 的数据，保证：
$0 \le n \le 10^9$
$1\le k \le 2000$
$d\in \{ 1,2,3,4,6 \}$

By：EntropyIncreaser