P5548 [BJ United Round #3] 押韵
题目背景
韵要怎么押？棋要怎么下？敌要怎么杀？旗要怎么插？
题目描述
现在你想要写一首歌词，一共有 $nd$ 个字，你一共设计了 $k$ 种韵脚，每个字恰好要符合一种韵脚。
并且只有当每种韵脚在歌词中出现的字数恰为 $d$ 的倍数时，这首歌才好听。
试问一共有多少种韵脚的搭配方法，使得歌词好听？
你只需要回答方案数对于 $1049874433$ 取模的结果即可。
输入格式
无
输出格式
无
说明/提示
对于 $100\%$ 的数据，保证：
$0 \le n \le 10^9$
$1\le k \le 2000$
$d\in \{ 1,2,3,4,6 \}$
By：EntropyIncreaser