← 返回题目列表

Codeforces · 1061/C

C. 多重性

中文机器翻译题面 查看原题

给你一个整数数组 $$$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\}$$$。

请注意,某些子序列会多次列出,因为它们在原始数组中出现多次。