#P18440. Go go Baron Bunny!
Go go Baron Bunny!
Go go Baron Bunny!

Bad Frog 不愿意为程序设计竞赛投入太多精力,只愿意提供 个脑细胞来记忆竞赛知识点。
今天早上,队友发现他记得 个知识点,它们分别占用 个脑细胞。每个仍记得的知识点占用正整数个脑细胞,总占用不超过 。
由于 Bad Frog 几乎不练习,白天每个知识点所占用的脑细胞数都会减少 ;减为 的知识点就会被遗忘。
每到晚上,队友发现他又没有练习、用于记忆知识点的脑细胞减少了,就会督促他使用全部剩余脑细胞学习一个新的知识点。
例如,若总共提供 个脑细胞,早上各知识点分别占用
那么晚上先变为
其中两个占用 个脑细胞的知识点被遗忘。最后,在队友的督促下,他用剩余的全部 个脑细胞学习一个新知识点,于是各知识点的占用变为
记多重集合 。离比赛还有 天。为了让他发挥稳定,队友希望 天后比赛当天的这个多重集合与今天完全相同。
求满足要求的有序数组 的数量,对 取模。每天的演化条件比较的是多重集合;统计时,不同顺序的数组分别计数。
输入格式
输入一行三个整数 ,满足
它们分别是脑细胞总数、今天早上的知识点数量,以及距离比赛的天数。
输入只有一个测试实例,不输入数组 。
输出格式
输出一个整数,表示满足要求的数组数量对 取模的结果。
样例 1
2 1 2
1
样例 2
8 4 2
6
样例 3
29 7 154
0
样例 4
50 10 10
77225400
样例说明
第一个样例中,唯一的数组是 ,其变化为
第二个样例中,六个数组为
$$[1,1,3,3],\ [1,3,1,3],\ [1,3,3,1],\ [3,1,1,3],\ [3,1,3,1],\ [3,3,1,1].$$