C. Multiplicity
data structures; dp; implementation; math; number theory
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.