Multiplicity

题意翻译

从序列 $\{a_1,\ a_2,\ ..\ ,\ a_n\}$ 中选出**非空**子序列 $\{b_1,\ b_2,\ ..\ ,\ b_k\}$，一个子序列合法需要满足 $\forall\ i \in [1,\ k],\ i\ |\ b_i$。求有多少互不相等的合法子序列，答案对 $10^9 + 7$ 取模。 序列 $\{1,\ 1\}$ 有 $2$ 种选法得到子序列 $\{1\}$，但 $1$ 的来源不同，认为这两个子序列不相等。

题目描述

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

输入输出样例

输入样例 #1

2
1 2

输出样例 #1

3

输入样例 #2

5
2 2 1 22 14

输出样例 #2

13

说明

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.