Codeforces Round 523 (Div. 2) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

data structures

dp

implementation

math

number theory

*1700

No tag edit access

The problem statement has recently been changed. View the changes.

×
C. Multiplicity

time limit per test

3 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou 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).

Input

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

Output

Print exactly one integer — the number of good subsequences taken modulo $$$10^9 + 7$$$.

Examples

Input

2

1 2

Output

3

Input

5

2 2 1 22 14

Output

13

Note

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.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/24/2024 00:18:36 (j3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|