#P13849. [diverta2019_2]Balanced Piles
[diverta2019_2]Balanced Piles
题目描述
有 个格子横向排列,从左到右依次编号为 到 。高桥君打算在这些格子上堆积木。初始时,每个格子上都没有积木。
高桥君希望将积木堆得均匀,他会重复以下操作,直到每个格子上都恰好堆有 个积木为止:
- 设当前所有格子中积木数的最大值为 ,最小值为 。从所有积木数为 的格子中任选一个(如果有多个可以任选),在该格子上堆若干个积木,使得该格子的积木数变为 以上且不超过 ,即堆到 、、、 中的某一个数。
请你帮高桥君计算,经过若干次上述操作后,使所有格子上都恰好有 个积木的方法总数。由于答案可能非常大,请输出对 取模后的结果。
输入格式
输入为一行,包含三个整数:
输出格式
输出使所有格子上都恰好有 个积木的方法总数,对 取模。
输入输出样例 #1
输入 #1
2 2 1
输出 #1
6
输入输出样例 #2
输入 #2
2 30 15
输出 #2
94182806
输入输出样例 #3
输入 #3
31415 9265 3589
输出 #3
312069529
说明/提示
限制条件
- 输入均为整数
样例解释 1
(格子 上的积木数,格子 上的积木数)可以按如下方式变化:
因此,使所有格子上都恰好有 个积木的方法总数为 。
样例解释 3
注意要输出对 取模后的结果。