#P17960. Stonebag
Stonebag
Stonebag
有 堆石子,编号为 到 ,第 堆最初有 颗石子。你还有一个最初为空的袋子。
可以以任意顺序执行以下操作任意多次:
- 选择一堆非空的石子,从中取出一颗,放进袋子。
- 选择一堆石子(可以为空),从袋子里取出恰好 颗石子,全部放入这一堆。只有袋子里至少有 颗石子时才能执行此操作。
你可以随时停止操作。结束时袋子里允许留有任意数量的石子,包括非零数量。
求通过有限次操作可以得到多少种不同的石子堆最终状态,答案对 取模。 如果存在某个编号的石子堆在两种状态中的石子数不同,则这两种状态不同。石子堆有标号,顺序不能忽略。
输入格式
第一行一个整数 ()。
第二行 个整数 ()。
输出格式
输出一个整数,表示不同最终状态数对 取模的结果。
样例 1
输入
2
1 3
输出
15
样例 2
输入
3
2 1 3
输出
83
样例 3
输入
8
4 3 6 5 2 0 6 3
输出
37238603