CF1061C.Multiplicity

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).

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$ ).

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

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.