Migrated from Lutece 3170 分饼干

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

"我要成为acm高手....嘿嘿"

“醒醒帕鲁，上班了”

还在做白日梦的小u同学被老板叫醒，并被要求去干活.

老板给了你$n$袋饼干，每袋饼干装有$a_i$个饼干，用于招待今天的客人.

今天的客人对于饼干数和顺序格外敏感，当给第$i$个人分发饼干时，要遵循以下规则:

1.必须按顺序从剩下的第一袋饼干连续取$k$袋饼干分发给客人，$k$为不超过当前袋数的正整数.

2.保证这$k$袋饼干的饼干总数能被$i$整除.

3.当所有饼干被分完后不接待客人$i$，并视为分配完成.

由于你上班摸鱼，老板还要求你计算出所有分配方案的总数$sum$是多少(每种方案都必须分配完成).

小u同学犯了难，于是找身怀绝技的你来帮忙计算$sum$是多少，毕竟他也不想丢掉工作.

由于方案数可能非常多，因此你只需要输出$sum$对$10^9+7$取模的结果

两个分配方案中存在有一袋饼干分给不同的客人时，视为两种不同的方案.

Input

第一行输入一个正整数$n$，表示饼干袋数. 第二行输入正整数序列$a_1,a_2,a_3,\cdots,a_n$，其中$a_i$表示第$i$袋饼干的饼干个数.

Output

输出一个数，即$sum$对$10^9+7$取模的结果

Samples

4
1 2 3 4

3

5
8 6 3 3 3

5

Constraints

$1\leq n\leq3000$, $1\leq a_i \leq 10^{15}$

Note

样例一解释: 分配方案一共三种，具体如下: "()"中的内容表示第$i$个客人拿到的袋装饼干的编号集合 方案一: 客人1:$(1)$, 客人2:$(2)$, 客人3:$(3)$, 客人4:$(4)$. 方案一: 客人1:$(1,2,3)$, 客人2:$(4)$. 方案三: 客人1:$(1,2,3,4)$.

Resources

2024 UESTC ICPC Training for Search and Dynamic Programming