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


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

Difficulty: interview

Starter code:

Solutions:
import math
n = int(input())
a = list(map(int, input().split()))
d = {0: 1}
m = 1
ans = 0
for i in a:
	#print("i=", i)
	divisors = []
	for j in range(1, min(m, int(math.sqrt(i))) + 1):
		if i % j == 0:
			k = int(i / j)
			divisors.append(j)
			if j != k and k <= m:
				divisors.append(k)
	#print("divisors=", divisors)
	new_d = {0: 1}
	for j in divisors:
		ans = (ans + d[j - 1]) % 1000000007
		#print("j=", j, "ans=", ans)
		new_d[j] = d.get(j, 0) + d[j - 1]
		if j == m:
			m = m + 1
	#print("new_d=", new_d)
	for j in new_d:
		d[j] = new_d[j]
print(ans)

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 ret[::-1]

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

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

    # print(dp)
    return (sum(dp)-1) % int(1e9+7)

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

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

def __starting_point():
    ipt = intRead()
    n = next(ipt)
    lis = [next(ipt) for _ in range(n)]
    print(solve(n, lis))

__starting_point()

import math

def nextDiv(a):
    tmp = []
    sq = int(math.sqrt(a))
    for i in range(1, sq+1):
        if (a%i == 0):
            j = a//i
            yield j
            if (i != j):
                tmp.append(i)

    while tmp:
        yield tmp.pop()

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] = 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

def __starting_point():
    ipt = intRead()
    n = next(ipt)
    lis = [next(ipt) for _ in range(n)]
    print(solve(n, lis))

__starting_point()

import math

def nextDiv(a):
    tmp = []
    sq = int(math.sqrt(a))
    for i in range(1, sq+1):
        if (a%i == 0):
            j = a//i
            yield j
            if (i != j):
                tmp.append(i)

    while tmp:
        yield tmp.pop()

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

def __starting_point():
    ipt = intRead()
    n = next(ipt)
    lis = [next(ipt) for _ in range(n)]
    print(solve(n, lis))

__starting_point()

import math

def nextDiv(a):
    tmp = set()
    sq = int(math.sqrt(a))
    for i in range(1, sq+1):
        if (a%i == 0):
            tmp.add(i)
            tmp.add(a//i)

    return reversed(sorted(tmp))

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

def __starting_point():
    ipt = intRead()
    n = next(ipt)
    lis = [next(ipt) for _ in range(n)]
    print(solve(n, lis))

__starting_point()

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 ret[::-1]

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

def __starting_point():
    ipt = intRead()
    n = next(ipt)
    lis = [next(ipt) for _ in range(n)]
    print(solve(n, lis))

__starting_point()

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

def __starting_point():
    ipt = intRead()
    n = next(ipt)
    lis = [next(ipt) for _ in range(n)]
    print(solve(n, lis))

__starting_point()

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 ret[::-1]

MOD = int(1e9+7)
from functools import reduce
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


    dp[0]=0
    return reduce(lambda a,b: (a+b)%MOD, dp)

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

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

def __starting_point():
    ipt = intRead()
    n = next(ipt)
    lis = [next(ipt) for _ in range(n)]
    print(solve(n, lis))

__starting_point()

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)
from functools import reduce
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


    dp[0]=0
    return reduce(lambda a,b: (a+b)%MOD, dp)

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

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

def __starting_point():
    ipt = intRead()
    n = next(ipt)
    lis = [next(ipt) for _ in range(n)]
    print(solve(n, lis))

__starting_point()

#multiplicity
n=int(input())
a=[int(x) for x in input().split()]

hell=10**9+7
dp=[0]*(n+5)
dp[0]=1
import math
for i,x in enumerate(a):
	
	j=1
	t_dp={}
	while j<=min(i+1,int(math.sqrt(x))):
		
		if(x%j == 0):
			t_dp[j]=(dp[j]+dp[j-1])%hell
			if(x//j != j and x//j <=(i+1)):
				t_dp[x//j]=(dp[x//j] + dp[ (x//j) -1])%hell
			
		j+=1
	
	for e in list(t_dp.keys()):
		dp[e]=t_dp[e]
	

ans=0
for i in dp[1:]:
    ans =(ans+ i)%hell
print(ans%hell)





import math
n = int(input())
a = list(map(int,input().split()))
dp = [0]*(n+1)
dp[0]=1
mod = int(1e9 +7)
for el in a:
	sqrt = int(math.sqrt(el))
	for d in range(min(n,sqrt),0,-1):
		if el%d==0:
			if el/d > sqrt and el/d<=n:
				dp[el//d]= (dp[el//d] + dp[el//d-1])%mod
			dp[d]= (dp[d]+dp[d-1])%mod
res=0
for i in range(1,n+1):
	res = (res+dp[i])%mod
print(res)

#import numpy as np
import bisect

def main(n,s,mod):
    ls = len(s)
    L = [[] for i in range(n+1)]
    for i,x in enumerate(s):
        L[x].append(i)
    for i in range(1,ls+1):
        for j in range(2*i,n+1,i):
            L[i] += L[j]
        L[i].sort()
    L = L[:ls+1]

    counts = [list(range(ls)),[1 for i in range(ls)]]
    S = ls
    for d in range(2,ls+1):
        if not L[d]: break
        lcounts = len(counts[0])
        sumcounts = [0]
        for i in range(1,lcounts+1):
            sumcounts.append((sumcounts[i-1] + counts[1][i-1]) % mod)
        newcounts = [[],[]]
        for x in L[d]:
            y = sumcounts[bisect.bisect_left(counts[0],x)]
            S = (S + y) % mod
            newcounts[0].append(x), newcounts[1].append(y)
        counts = newcounts
    return S

useless = str(input()).split(' ')
s = [int(i) for i in input().split(' ')]
n = 10**6
mod = 10**9 + 7
#k = 10**5
#s = [0]*(2*k)
#s[0:2*k:2] = list(range(1,k+1))
#s[1:2*k:2] = list(range(1,k+1))
print(main(n,s,mod))


n=int(input())
a=list(map(int,input().split()))
dp=[0]*(1000001)
dp[0]=1
for i in range(n):
    x=int(a[i]**.5)
    for j in range(min(i+1,x),0,-1):
        if a[i]%j==0:
            if a[i]/j>x and a[i]/j<=n:
                dp[a[i]//j]+=dp[a[i]//j-1]
            dp[j]+=dp[j-1]
ans=0
for i in range(1,n+1):
    ans+=dp[i]
    ans%=1000000007
print(ans)

#	!/bin/env python3
#	coding: UTF-8


#	✪ H4WK3yE乡
#	Mohd. Farhan Tahir
#	Indian Institute Of Information Technology and Management,Gwalior

#	Question Link
#	https://codeforces.com/problemset/problem/1061/C
#

# ///==========Libraries, Constants and Functions=============///


import sys

inf = float("inf")
mod = 1000000007


def get_array(): return list(map(int, sys.stdin.readline().split()))


def get_ints(): return list(map(int, sys.stdin.readline().split()))


def input(): return sys.stdin.readline()

# ///==========MAIN=============///


def factors(n):
    curr = []
    j = 1
    while j*j <= n:
        if n % j == 0:
            curr.append(j)
            if j != n//j:
                curr.append(n//j)
        j += 1
    curr.sort(reverse=True)
    return curr


def main():
    n = int(input())
    dp = [0 for _ in range(1000005)]
    arr = get_array()
    for i in range(n):
        x = factors(arr[i])
        for j in range(len(x)):
            if x[j] == 1:
                continue
            dp[x[j]] += dp[x[j]-1]
            dp[x[j]] %= mod
        dp[1] += 1
    ans = 0
    for i in range(1000005):
        ans += dp[i]
    ans %= mod
    print(ans)


def __starting_point():
    main()

__starting_point()

#	!/bin/env python3
#	coding: UTF-8


#	✪ H4WK3yE乡
#	Mohd. Farhan Tahir
#	Indian Institute Of Information Technology and Management,Gwalior

#	Question Link
#	https://codeforces.com/problemset/problem/1061/C
#

# ///==========Libraries, Constants and Functions=============///


import sys

inf = float("inf")
mod = 1000000007


def get_array(): return list(map(int, sys.stdin.readline().split()))


def get_ints(): return list(map(int, sys.stdin.readline().split()))


def input(): return sys.stdin.readline()

# ///==========MAIN=============///


def factors(n):
    curr = []
    j = 1
    while j*j <= n:
        if n % j == 0:
            curr.append(j)
            if j != n//j:
                curr.append(n//j)
        j += 1
    curr.sort(reverse=True)
    return curr


def main():
    n = int(input())
    dp = [0 for _ in range(1000005)]
    dp[0] = 1
    arr = get_array()
    for i in range(n):
        x = factors(arr[i])
        for j in range(len(x)):
            dp[x[j]] += dp[x[j]-1]
            dp[x[j]] %= mod

    ans = 0
    for i in range(1, n+1):
        ans += dp[i]
    ans %= mod
    print(ans)


def __starting_point():
    main()

__starting_point()

n = int(input())
a = list(map(int, input().split()))
N = 1000005
MOD = 10 ** 9 + 7
dp =[0] * N
dp[0] = 0
for i in range(n):
    cur = []
    A = int(a[i] ** 0.5) + 1
    for j in range(1, A):
        if a[i] % j == 0:
            cur.append(j)
            if a[i] // j != j:
                cur.append(a[i] // j)

    cur = sorted(cur, reverse=True)
    for j in cur:
        if j == 1:
            dp[j] += 1
        else:
            dp[j] += dp[j - 1]

ans = 0
for i in dp:
    ans += i
    ans %= MOD
print(ans)


n=int(input())
a=list(map(int,input().split()))
seen=[0]*(n+3)
long=1
for guy in a:
    if guy**0.5>long-50:
        for i in range(long+1,1,-1):
            if guy%i==0:
                seen[i]+=seen[i-1]
                if i==long+1:
                    long+=1
    else:
        facs=[]
        bigfacs=[]
        for i in range(1,int(guy**0.5)+1):
            if guy%i==0:
                facs.append(i)
                bigfacs.append(guy//i)
        if facs[-1]==bigfacs[-1]:
            bigfacs.pop()
        facs+=bigfacs[::-1]
        for guy1 in facs[::-1]:
            if guy1<=long+1:
                seen[guy1]+=seen[guy1-1]
                if guy1==long+1:
                    long+=1          
    seen[1]+=1
print(sum(seen)%1000000007)

MOD = int(1e9 + 7)

N = int(input())
A = list(map(int, input().split()))
ways = [0] * (N + 1)
ways[0] = 1

for a in A:
    factors = []
    big_factors = []
    x = 1

    while x * x <= a:
        if a % x == 0:
            factors.append(x)

            if x * x < a:
                big_factors.append(a // x)

        x += 1

    factors.reverse()

    for x in big_factors:
        if x <= N:
            ways[x] += ways[x - 1]

            if ways[x] >= MOD:
                ways[x] -= MOD

    for x in factors:
        if x <= N:
            ways[x] += ways[x - 1]

            if ways[x] >= MOD:
                ways[x] -= MOD

print((sum(ways) - 1) % MOD)


import math
from collections import defaultdict

n = int(input())
arr = list(map(int,input().strip().split()))

MOD = 1000000007

pre = defaultdict(int)

def get_divisors(k, upper):
  div = []
  for i in range(2, min(upper, int(math.floor(math.sqrt(k)))) + 1):
    if k % i == 0:
      div.append(i)
      if k // i <= upper:
        div.append(k // i)
  if k <= upper:
    div.append(k)
  return div

for i in range(n):
  div = get_divisors(arr[i], i+1)
  update = {}
  for d in div:
    if pre[d-1] == 0:
      continue
    update[d] = (pre[d] + pre[d-1]) % MOD
  pre.update(update)
  pre[1] += 1

print(sum(pre.values()) % MOD)

n = int(input())
A = [int(i) for i in input().split()]

def fct(x):
    ans = []
    for i in range(1, x+1):
        if i*i>x:
            break
        if x%i==0:
            ans.append(i)
            if i*i!=x:
                ans.append(x//i)
    return sorted(ans)[::-1]

dp = [0 for i in range(10**6 + 5)]

mod = 10**9 + 7

dp[0] = 1
for i in A:
    do = fct(i)
    for j in do:
        dp[j] = (dp[j]+dp[j-1])%mod

c = 0
for i in dp:
    c+=i
    if c>=mod:
        c-=mod
        
print((c-1)%mod)


import math
from functools import reduce
n = int(input())
 
lis = [int(x) for x in input().split()]
dic = {0:0,1:0,2:0}
max_num = 2
for j,i in enumerate(lis):
    
    temp_dic = {}
    lis = set()
    for k in range(1,math.ceil(math.sqrt(i))+2):
        if i%k == 0:
            lis.add(k)
            if i % i//k ==0:
                lis.add(i//k)
    
    for k in lis:
        if (k-1) in dic:
            temp_dic[k]=(temp_dic.get(k,0)+dic.get(k-1)) % 1000000007
    for k in list(temp_dic.keys()):
        
        dic[k]=dic.get(k,0)+temp_dic[k]
                
                
    dic[1]+=1 
su = 0
#print(dic)
for i in list(dic.keys()):
    su += dic[i] % 1000000007
 
print(su%1000000007)



def getFacts(n):
    facts = []
    for i in range(1,int(n**0.5)+1):
        if n%i == 0:
            facts.append(i)
            if i != n//i:
                facts.append(n//i)

    return facts

def main():
    n = int(input())
    arr = list(map(int,input().split()))

    dp = [0]*(n+1)
    mod = 10**9+7

    for i in arr:
        facts = getFacts(i)
        vals = {}
        for j in facts:
            if j <= n:
                vals[j] = dp[j-1]

        for j in facts:
            if j <= n:
                dp[j] += vals[j]
                dp[j] %= mod

        dp[1] += 1

    #print(dp)
    total = sum(dp)%mod

    print(total)


main()


from sys import stdin
from collections import deque
mod = 10**9 + 7
import sys
# sys.setrecursionlimit(10**5)
# def rl():
#     return [int(w) for w in stdin.readline().split()]
from bisect import bisect_right
from bisect import bisect_left
from collections import defaultdict
from math import sqrt,factorial,gcd,log2,inf,ceil
# map(int,input().split())
# # l = list(map(int,input().split()))
# from itertools import permutations
import heapq
# input = lambda: sys.stdin.readline().rstrip()
input = lambda : sys.stdin.readline().rstrip()
from sys import stdin, stdout
from heapq import heapify, heappush, heappop


n = int(input())

l = list(map(int,input().split()))
def solve(n):

    for i in range(1,int(sqrt(n))+1):
        if n%i == 0:
            hash[n].add(i)
            hash[n].add(n//i)

    hash[n] = sorted(list(hash[n]))[::-1]

hash = defaultdict(set)
dp = [0]*(10**6 + 1)
dp[0] = 1
for i in l:
    if hash[i] == set():
        solve(i)

        for j in hash[i]:
            dp[j] = dp[j]%mod + dp[j-1]%mod
            dp[j]%=mod
    else:
        for j in hash[i]:
            dp[j] = dp[j]%mod + dp[j-1]%mod
            dp[j]%=mod

# print(dp)
print(sum(dp[1:])%mod)