Cho dãy \(A\) gồm \(n\) số nguyên dương. Hãy lập trình đếm số cách chia dãy \(A\) thành \(k\) đoạn liên tiếp không giao nhau \(B_1\), \(B_2\),..., \(B_k\) sao cho với mọi \(i\) (\(1\leq i\leq k\)), tổng của các phần tử trong đoạn \(B_i\) chia hết cho \(i\). Vì kết quả có thể rất lớn nên bạn chỉ cần in ra phần dư của nó khi chia cho \(10^9+7\).

Input

Dòng đầu chứa số nguyên dương \(n\) - độ dài của dãy.

Dòng tiếp theo chứa \(n\) số nguyên \(A_1\), \(A_2\),..., \(A_n\) thể hiện các phần tử của dãy.

Output

Một số nguyên duy nhất là kết quả của bài toán.

Ví dụ

Sample Input 1

4
1 2 3 4

Sample Output 1

3

Giải thích

Có ba cách chia như sau:

• \((1),(2),(3),(4)\).
• \((1,2,3),(4)\).
• \((1,2,3,4)\).

Sample input 2

5
8 6 3 3 3

Sample output 2

5

Ràng buộc

• \(1 \leq n \leq 3000\).
• \(1 \leq A_i \leq 10^{15}\).