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