1061_C. Multiplicity
You are given an integer array a_1, a_2, …, 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, …, b_k is called to be good if it is not empty and for every i (1 ≤ i ≤ 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 ≤ n ≤ 100 000) — the length of the array a.

The next line contains integers a_1, a_2, …, a_n (1 ≤ a_i ≤ 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.
```python
import math

def nextDiv(a):
    ret = []
    i = 1;
    while (i*i <= a):
        if (a%i == 0):
            ret.append(i)
            j = a//i
            if (i != j):
                ret.append(j)
        i += 1
    return reversed(ret)

MOD = int(1e9+7)

def solve(n, lis):
    dp = [0] * (max(lis)+1)
    dp[0] = 1

    for i in lis:
        for j in nextDiv(i):
            dp[j] += dp[j-1]
            dp[j] %= MOD

    return (sum(dp)-1) % MOD

###########################
###########################

from sys import stdin
def intRead():
    while True:
        ln = stdin.readline().strip()
        if not ln:
            return
        for i in map(int, ln.split()):
            yield i

if __name__ == "__main__":
    ipt = intRead()
    n = next(ipt)
    lis = [next(ipt) for _ in range(n)]
    print(solve(n, lis))

```