Multiplicity

3000ms

262144K

Description:

You are given an integer array $$$a_1, a_2, \ldots, a_n$$$.

The array $$$b$$$ is called to be a subsequence of $$$a$$$ if it is possible to remove some elements from $$$a$$$ to get $$$b$$$.

Array $$$b_1, b_2, \ldots, b_k$$$ is called to be good if it is not empty and for every $$$i$$$ ($$$1 \le i \le k$$$) $$$b_i$$$ is divisible by $$$i$$$.

Find the number of good subsequences in $$$a$$$ modulo $$$10^9 + 7$$$.

Two subsequences are considered different if index sets of numbers included in them are different. That is, the values of the elements do not matter in the comparison of subsequences. In particular, the array $$$a$$$ has exactly $$$2^n - 1$$$ different subsequences (excluding an empty subsequence).

Input:

The first line contains an integer $$$n$$$ ($$$1 \le n \le 100\,000$$$) — the length of the array $$$a$$$.

The next line contains integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^6$$$).

Output:

Print exactly one integer — the number of good subsequences taken modulo $$$10^9 + 7$$$.

Sample Input:

2
1 2

Sample Output:

Sample Input:

5
2 2 1 22 14

Sample Output:

Note:

In the first example, all three non-empty possible subsequences are good: $$$\{1\}$$$, $$$\{1, 2\}$$$, $$$\{2\}$$$

In the second example, the possible good subsequences are: $$$\{2\}$$$, $$$\{2, 2\}$$$, $$$\{2, 22\}$$$, $$$\{2, 14\}$$$, $$$\{2\}$$$, $$$\{2, 22\}$$$, $$$\{2, 14\}$$$, $$$\{1\}$$$, $$$\{1, 22\}$$$, $$$\{1, 14\}$$$, $$$\{22\}$$$, $$$\{22, 14\}$$$, $$$\{14\}$$$.

Note, that some subsequences are listed more than once, since they occur in the original array multiple times.

Informação

Provedor Codeforces

Código CF1061C