给你一个整数数组 $$$a_1, a_2, \ldots, a_n$$$。
如果可以从 $$$a$$$ 中删除一些元素以获得 $$$b$$$,则数组 $$$b$$$ 被称为 $$$a$$$ 的子序列。
数组 $$$b_1, b_2, \ldots, b_k$$$ 如果不为空,并且对于每个 $$$i$$$ ($$$1 \le i \le k$$$) $$$b_i$$$ 可以被 $$$i$$$ 整除,则该数组被称为良好。
求 $$$a$$$ 模 $$$10^9 + 7$$$ 中的好子序列的数量。
如果两个子序列中包含的数字索引集不同,则认为两个子序列不同。也就是说,元素的值在子序列的比较中并不重要。特别是,数组 $$$a$$$ 恰好有 $$$2^n - 1$$$ 个不同的子序列(不包括空子序列)。
输入
第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 100\,000$$$) — 数组 $$$a$$$ 的长度。
下一行包含整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^6$$$)。
输出
精确打印一个整数——以 $$$10^9 + 7$$$ 为模的好子序列的数量。
示例
输入 #1
2 1 2
输出 #1
3
输入 #2
5 2 2 1 22 14
输出 #2
13
注意
在第一个示例中,所有三个非空可能子序列都很好:$$$\{1\}$$$、$$$\{1, 2\}$$$、$$$\{2\}$$$
在第二个例子中,可能的好子序列是: $$$\{2\}$$$, $$$\{2, 2\}$$$, $$$\{2, 22\}$$$, $$$\{2, 14\}$$$, $$$\{2\}$$$, $$$\{2, 22\}$$$, $$$\{2, 14\}$$$、$$$\{1\}$$$、$$$\{1, 22\}$$$、$$$\{1, 14\}$$$、$$$\{22\}$$$、$$$\{22、14\}$$$、$$$\{14\}$$$。
请注意,某些子序列会多次列出,因为它们在原始数组中出现多次。