[BJ United Round #3] 押韵
题目背景
韵要怎么押?棋要怎么下?敌要怎么杀?旗要怎么插?
题目描述
现在你想要写一首歌词,一共有 $nd$ 个字,你一共设计了 $k$ 种韵脚,每个字恰好要符合一种韵脚。
并且只有当每种韵脚在歌词中出现的字数恰为 $d$ 的倍数时,这首歌才好听。
试问一共有多少种韵脚的搭配方法,使得歌词好听?
你只需要回答方案数对于 $1049874433$ 取模的结果即可。
输入输出格式
输入格式
一行三个整数 $n,k,d$,如题意所示。
输出格式
一行一个整数,表示答案。
输入输出样例
输入样例 #1
2 2 2
输出样例 #1
8
输入样例 #2
2 3 4
输出样例 #2
213
输入样例 #3
2 4 6
输出样例 #3
5548
说明
![](https://i.niupic.com/images/2019/09/08/_49.png)
对于 $100\%$ 的数据,保证:
$0 \le n \le 10^9$
$1\le k \le 2000$
$d\in \{ 1,2,3,4,6 \}$
By:EntropyIncreaser