2017.8.17 ACM 训练赛

H. 刚好坐满的公交车

单点时限: 3.0 sec

内存限制: 256 MB

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

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

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

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

输入格式

第一行一个整数 $n$ $(1 \leq n \leq 500~000)$。

第二行 $n$ 个整数,用空格隔开,分别为 $a_1, a_2, \ldots, a_n$ $(1 \leq a_i \leq 500~000)$。

输出格式

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

样例

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

提示

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

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