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.