3326. 刚好坐满的公交车

单点时限: 3.0 sec

内存限制: 256 MB

组小学生在公交车站前排队,第 组有 个人。

这时候车站来了一辆空车,排在前面的小学生就走上公交车。当然,同一组的小学生不想分开,他们必须坐同一辆公交车。然而,公交车为了考虑成本,只有在坐满的时候才会开。排队的小学生们不会插队,要是前面的小学生不走,后面的也只会乖乖地等着。

结果,小学生们一个都没有离开——于是,他们等到了第二天……

第二天,公交车公司决定调整公交车的容量,使得每辆公交车刚好能坐 个人,并让小学生们都能回家。问 共有多少种可能的取法。结果可能很大,模

输入格式

第一行一个整数

第二行 个整数,用空格隔开,分别为

输出格式

输出方案数对 取模后的结果。

样例

Input
6
1 1 1 1 1 1
Output
4
Input
3
1 2 3
Output
2

提示

样例 1:公交车容量是 ,都是可行的。

样例 2:有两种方案:容量为 的公交车,第一辆载 ,第二辆载 ;或者容量为 的公交车,一次性全部载完。

9 人解决,14 人已尝试。

11 份提交通过,共有 33 份提交。

6.4 EMB 奖励。

创建: 2 年,2 月前.

修改: 2 年,1 月前.

最后提交: 3 月,1 周前.

来源: HackerRank

题目标签