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: MEDIUM_HARD
Tags: Implementation

Number theory

Dynamic programming

Mathematics

Data structures
Skill types: Dynamic programming

Data structures

Starter code:

Solutions:
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]
	return (sum(dp) - 1) % int(1000000000.0 + 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
ipt = intRead()
n = next(ipt)
lis = [next(ipt) for _ in range(n)]
print(solve(n, lis))


from math import ceil, sqrt
mod = 10 ** 9 + 7

def div(n):
	x = set()
	for i in range(ceil(sqrt(n)), 0, -1):
		if n % i == 0:
			x.add(n // i)
			if n // i != i:
				x.add(i)
	return sorted(list(x), reverse=True)
n = int(input())
a = [int(x) for x in input().split()]
dp = [0] * (n + 1)
dp[0] = 1
for i in range(n):
	for j in div(a[i]):
		if j <= n:
			dp[j] = (dp[j] + dp[j - 1]) % mod
an = 0
for i in range(1, len(dp)):
	an = (an + dp[i]) % mod
print(an)


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)


MOD = int(1000000000.0 + 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 os, sys, math
from io import BytesIO, IOBase
from collections import defaultdict, deque, OrderedDict
import bisect as bi

def yes():
	print('YES')

def no():
	print('NO')

def I():
	return int(input())

def In():
	return map(int, input().split())

def ln():
	return list(map(int, input().split()))

def Sn():
	return input().strip()
BUFSIZE = 8192

def find_gt(a, x):
	i = bi.bisect_left(a, x)
	if i != len(a):
		return i
	else:
		return len(a)

def divs(n):
	div = []
	for i in range(1, int(math.sqrt(n)) + 1):
		if n % i == 0:
			div.append(i)
			if i * i != n:
				div.append(n // i)
	return div

def solve():
	n = I()
	l = list(In())
	dp = {}
	dp[0] = 1
	total = 0
	for i in range(n):
		t = divs(l[i])
		for j in t:
			if dp.get(j - 1, -1) != -1:
				total += dp[j - 1] % P
				total %= P
		temp_dp = {}
		for j in t:
			if j > i + 1:
				continue
			if dp.get(j - 1, -1) != -1:
				if dp.get(j, -1) != -1:
					temp_dp[j] = dp[j - 1] + dp[j]
				else:
					temp_dp[j] = dp[j - 1]
		for j in temp_dp:
			dp[j] = temp_dp[j]
	print(total)
	pass

def main():
	for i in range(1):
		solve()
M = 998244353
P = 1000000007

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush, heappop
import math
from collections import *
from functools import reduce, cmp_to_key, lru_cache
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
M = mod = 10 ** 9 + 7

@lru_cache(None)
def factors(n):
	return sorted(set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0))))

def inv_mod(n):
	return pow(n, mod - 2, mod)

def li():
	return [int(i) for i in input().rstrip().split()]

def st():
	return str(input().rstrip())[2:-1]

def val():
	return int(input().rstrip())

def li2():
	return [str(i)[2:-1] for i in input().rstrip().split()]

def li3():
	return [int(i) for i in st()]
facts = defaultdict(list)
n = val()
l = li()
for i in l:
	if i:
		facts[i] = factors(i)[::-1]
d = defaultdict(int)
d[0] = 1
ans = 0
for i in l:
	for j in facts[i]:
		ans = (ans + d[j - 1]) % mod
		d[j] = (d[j] + d[j - 1]) % mod
print(ans)


import os
import sys
from io import BytesIO, IOBase

def main():
	n = int(input())
	a = list(map(int, input().split()))
	(ma, mod) = (max(a), 10 ** 9 + 7)
	b = [[] for _ in range(ma + 1)]
	for i in range(n):
		b[a[i]].append(i)
	c = list(range(n))
	d = [1] * n
	ans = n
	for i in range(2, n + 1):
		cc = []
		for j in range(i, ma + 1, i):
			z = b[j]
			while z and z[-1] < c[0]:
				z.pop()
			cc.extend(z)
		cc.sort()
		dd = [0] * len(cc)
		k = 0
		for j in range(len(c)):
			while k < len(cc) and cc[k] <= c[j]:
				k += 1
			if k < len(cc):
				dd[k] = (dd[k] + d[j]) % mod
		for j in range(1, len(cc)):
			dd[j] = (dd[j] + dd[j - 1]) % mod
		for j in range(len(cc)):
			ans = (ans + dd[j]) % mod
		c = cc
		d = dd
		if not len(c):
			break
	print(ans)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


mod = 10 ** 9 + 7
n = int(input())
arr = list(map(int, input().split()))
devBef = [0] * (max(arr) + 5)
deviders = []
ans = 0
for i in range(n):
	deviders.append([])
	iter = 2
	while iter * iter <= arr[i]:
		if arr[i] % iter == 0:
			if iter * iter == arr[i]:
				deviders[i].append(iter)
			else:
				deviders[i].append(arr[i] // iter)
				deviders[i].append(iter)
		iter += 1
	if arr[i] != 1:
		deviders[i].append(1)
	deviders[i].append(arr[i])
	deviders[i].sort()
for i in range(n):
	for g in range(len(deviders[i])):
		if deviders[i][g] == 1:
			ans += 1
		else:
			ans += devBef[deviders[i][g] - 1]
			ans %= mod
	for g in range(len(deviders[i]) - 1, -1, -1):
		if deviders[i][g] == 1:
			devBef[deviders[i][g]] += 1
		else:
			devBef[deviders[i][g]] += devBef[deviders[i][g] - 1]
			devBef[deviders[i][g]] %= mod
print(ans)


def divisors(n):
	div = []
	for i in range(1, int(n ** 0.5) + 1):
		if n % i == 0:
			if n // i == i:
				div.append(i)
			else:
				div.append(i)
				div.append(n // i)
	return div
from copy import copy
n = int(input())
arr = list(map(int, input().split()))
mod = int(1000000000.0 + 7)
dp = [0 for i in range(n + 1)]
dp[0] = 1
for i in range(1, n + 1):
	for j in sorted(divisors(arr[i - 1]), reverse=True):
		if j < n + 1:
			dp[j] = (dp[j] + dp[j - 1]) % mod
print(sum(dp[1:]) % mod)


import sys
input = sys.stdin.readline
from collections import defaultdict
n = int(input())
a = list(map(int, input().split()))
cnt = defaultdict(int)
cnt[0] = 1
MOD = 10 ** 9 + 7
for ai in a:
	l = []
	for i in range(1, int(ai ** 0.5) + 1):
		if ai % i == 0:
			l.append(i)
			if i != ai // i:
				l.append(ai // i)
	l.sort(reverse=True)
	for li in l:
		cnt[li] += cnt[li - 1]
		cnt[li] %= MOD
ans = 0
for v in cnt.values():
	ans += v
	ans %= MOD
print((ans - 1) % MOD)


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(1000000000.0 + 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
ipt = intRead()
n = next(ipt)
lis = [next(ipt) for _ in range(n)]
print(solve(n, lis))


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)


from sys import stdin
from collections import deque
mod = 10 ** 9 + 7
import sys
from bisect import bisect_right
from bisect import bisect_left
from collections import defaultdict
from math import sqrt, factorial, gcd, log2, inf, ceil
import heapq
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(sum(dp[1:]) % mod)


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 t_dp.keys():
		dp[e] = t_dp[e]
ans = 0
for i in dp[1:]:
	ans = (ans + i) % hell
print(ans % hell)


from math import sqrt
import sys
n = int(sys.stdin.readline())
a = [int(i) for i in sys.stdin.readline().split()]
maxi = int(sqrt(max(a))) + 1
dp = [0] * (max(a) + 1)
dp[0] = 1
mod = 10 ** 9 + 7
for i in range(n):
	fact = []
	for j in range(1, int(sqrt(a[i])) + 1):
		if a[i] % j == 0:
			fact.append(j)
			if j != a[i] // j:
				fact.append(a[i] // j)
	fact.sort(reverse=True)
	for j in fact:
		dp[j] += dp[j - 1]
		dp[j] %= mod
res = 0
for i in dp:
	res += i
	res %= mod
print(res - 1)


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)


n = int(input())
a = list(map(int, input().split()))
M = 10 ** 9 + 7
dp = [0 for i in range(10 ** 6 + 1)]
ans = 0
for i in range(n):
	temp = []
	for j in range(1, int(a[i] ** 0.5) + 1):
		if a[i] % j == 0:
			f1 = j
			f2 = a[i] // j
			if f1 == f2:
				if f1 == 1:
					ans += 1
					ans %= M
					temp.append([1, dp[1] + 1])
				else:
					ans += dp[f1 - 1]
					ans %= M
					temp.append([f1, dp[f1] + dp[f1 - 1]])
			else:
				if f1 == 1:
					ans += 1
					ans %= M
					temp.append([1, dp[1] + 1])
				else:
					ans += dp[f1 - 1]
					ans %= M
					temp.append([f1, dp[f1] + dp[f1 - 1]])
				if f2 == 1:
					ans += 1
					ans %= M
					temp.append([1, dp[1] + 1])
				else:
					ans += dp[f2 - 1]
					ans %= M
					temp.append([f2, dp[f2] + dp[f2 - 1]])
	for j in range(len(temp)):
		dp[temp[j][0]] = temp[j][1]
print(ans)


def getPrimes(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
	ret.reverse()
	return ret
n = int(input())
l = list(map(int, input().split()))
mod = 1000000007
arr = [0] * 1000001
arr[0] = 1
ans = 0
dp = [0] * (max(l) + 2)
dp[0] = 1
for i in range(n):
	primes = getPrimes(l[i])
	for j in primes:
		dp[j] += dp[j - 1]
print((sum(dp) - 1) % mod)


R = lambda : map(int, input().split())
mod = 10 ** 9 + 7
n = int(input())
arr = list(R())
bs = [list() for i in range(max(arr) + 1)]
for b in range(1, len(bs)):
	tmp = b
	while tmp < len(bs):
		bs[tmp].append(b)
		tmp += b
dp = [1] + [0] * n
for x in arr:
	for b in bs[x][::-1]:
		if b < len(dp):
			dp[b] = (dp[b] + dp[b - 1]) % mod
print(sum(dp[1:]) % mod)


import math
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def input():
	return sys.stdin.readline().rstrip('\r\n')
n = int(input())
l = list([int(x) for x in input().split()])
const = 1000000007
cnt = [0] * 1000001
cnt[0] = 1
for i in l:
	fact = []
	j = 1
	while j * j <= i:
		if i % j == 0:
			fact.append(j)
			if i // j != j:
				fact.append(i // j)
		j += 1
	fact.sort(reverse=True)
	for k in fact:
		cnt[k] += cnt[k - 1]
		cnt[k] %= const
sum = 0
for i in range(1, n + 1):
	sum += cnt[i]
sum %= const
print(sum)


import sys
input = sys.stdin.readline
mod = 10 ** 9 + 7
n = int(input())
a = list(map(int, input().split()))
fact = [[1] for i in range(1000001)]
b = max(a)
for i in range(2, b + 1):
	for j in range(i, b + 1, i):
		fact[j].append(i)
dp = [0] * (n + 1)
dp[0] = 1
for i in range(n):
	for j in range(len(fact[a[i]]) - 1, -1, -1):
		if fact[a[i]][j] <= i + 1:
			dp[fact[a[i]][j]] = (dp[fact[a[i]][j]] % mod + dp[fact[a[i]][j] - 1] % mod) % mod
print(sum(dp[1:]) % mod)


import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
ri = lambda : int(input())
rl = lambda : list(map(int, input().split()))
rs = lambda : input().decode().rstrip('\n\r')
from collections import deque as dq
inf = float('inf')
mod = 10 ** 9 + 7

def all_factors(n):
	(small, large) = ([], [])
	for i in range(1, int(n ** 0.5) + 1, 2 if n & 1 else 1):
		if not n % i:
			small.append(i)
			large.append(n // i)
	if small[-1] == large[-1]:
		large.pop()
	large.reverse()
	small.extend(large)
	return small
Cases = 1
for Case in range(Cases):
	n = ri()
	a = rl()
	multiplesof = [0 for i in range(10 ** 6 + 7)]
	multiplesof[0] = 1
	ans = 0
	for i in a:
		factors = all_factors(i)
		for i in factors[::-1]:
			multiplesof[i] += multiplesof[i - 1]
	for i in range(1, n + 1):
		ans += multiplesof[i]
		ans %= mod
	print(ans)


import math
n = int(input())
a = list(map(int, input().split()))
d = {0: 1}
m = 1
ans = 0
for i in a:
	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)
	new_d = {0: 1}
	for j in divisors:
		ans = (ans + d[j - 1]) % 1000000007
		new_d[j] = d.get(j, 0) + d[j - 1]
		if j == m:
			m = m + 1
	for j in new_d:
		d[j] = new_d[j]
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)


import sys
input = sys.stdin.buffer.readline
n = int(input())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7
d = dict()
d[0] = 1

def divisor(n):
	ass = []
	for i in range(1, int(n ** 0.5) + 1):
		if n % i == 0:
			ass.append(i)
			if i ** 2 == n:
				continue
			ass.append(n // i)
	return sorted(ass)
for i in range(n):
	tank = []
	for e in divisor(a[i]):
		if e > i + 1:
			break
		if e - 1 in d:
			tank.append((e, d[e - 1]))
	for (key, val) in tank:
		if key in d:
			d[key] = (d[key] + val) % mod
		else:
			d[key] = val
res = 0
for e in d:
	res = (res + d[e]) % mod
print((res - d[0]) % mod)


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
	total = sum(dp) % mod
	print(total)
main()


import os
import sys
import math
from io import BytesIO, IOBase
from fractions import Fraction
import collections
from itertools import permutations
from collections import defaultdict
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
n = int(input())
a = list(map(int, input().split()))
dp = [0] * 1000001
dp[0] = 1
for i in range(n):
	x = int(a[i] ** 0.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)


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
print(main(n, s, mod))


import sys
inf = float('inf')
mod = 1000000007

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

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

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

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)
main()


from sys import stdin, stdout
from math import *
from heapq import *

def divisors(x):
	global divisor, maxdv
	s = set([1])
	while x > 1:
		k = divisor[x]
		if k <= maxdv and k > 1:
			for y in s.copy():
				if y * k <= maxdv:
					s.add(y * k)
		x = floor(x / k)
	return list(s)

def main():
	global n, a, divisor, maxa, mod, maxdv
	mod = 10 ** 9 + 7
	n = int(stdin.readline())
	a = [int(x) for x in stdin.readline().split()]
	maxa = max(a) + 2
	divisor = [0] * (maxa + 2)
	fact = [1]
	for i in range(1, maxa):
		divisor[i] = i
		fact.append(fact[i - 1] * i % mod)
	for i in range(2, maxa):
		if divisor[i] == i:
			for j in range(i, maxa):
				if i * j > maxa:
					break
				divisor[i * j] = min(i, divisor[i * j])
	res = 0
	maxdv = 1
	f = [1] + [0] * maxa
	for x in a:
		ndv = divisors(x)
		ndv.sort(reverse=True)
		for dv in ndv:
			f[dv] = (f[dv] + f[dv - 1]) % mod
			res = (res + f[dv - 1]) % mod
			if f[dv] > 0:
				maxdv = max(maxdv, dv + 1)
	stdout.write(str(res))
	return 0
main()


import math
n = int(input())
li = [int(k) for k in input().split()]
dp = [0] * (n + 1)
dp[0] = 1
mod = 10 ** 9 + 7
for i in range(len(li)):
	x = int(math.sqrt(li[i]))
	for j in range(min(x, i + 1), 0, -1):
		if li[i] % j == 0:
			if li[i] // j > x and li[i] // j <= n:
				dp[li[i] // j] += dp[li[i] // j - 1] % mod
			dp[j] += dp[j - 1] % mod
ans = sum(dp[1:]) % mod
print(ans)


import math

def factors(n):
	ans = list()
	sqrt_n = math.floor(math.sqrt(n)) + 1
	for i in range(1, sqrt_n):
		if n % i == 0:
			ans.append(int(i))
			ans.append(int(n / i))
	return sorted(list(set(ans)), reverse=True)
n = int(input())
ai = [int(e) for e in input().split(' ')]
hash_ = [0] * 1000020
hash_[0] = 1
for a in ai:
	f_ai = factors(a)
	for f in f_ai:
		hash_[f] = (hash_[f] + hash_[f - 1]) % 1000000007
ans = sum(hash_[1:n + 1]) % 1000000007
print(ans)


n = int(input())
a = list(map(int, input().split()))
dp = [0] * (n + 5)
mod = 10 ** 9 + 7
dp[0] = 1
for i in range(n):
	x = int(a[i] ** 0.5)
	for j in range(min(i + 1, x), 0, -1):
		if a[i] % j == 0:
			if a[i] / j <= n and a[i] / j > x:
				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 %= mod
print(ans)


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
for i in list(dic.keys()):
	su += dic[i] % 1000000007
print(su % 1000000007)


n = int(input())
a = list(map(int, input().split()))
dp = [0] * 1000001
dp[0] = 1
for i in range(n):
	x = int(a[i] ** 0.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)


import math
n = int(input())
a = list(map(int, input().split()))
dp = [0] * (n + 1)
dp[0] = 1
mod = int(1000000000.0 + 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)


def get_prime(p):
	i = 1
	col = []
	while i * i <= p:
		if p % i == 0:
			col.append(i)
			if i != p // i:
				col.append(p // i)
		i += 1
	col.reverse()
	return col
n = int(input())
a = list(map(int, input().split()))
M = 10 ** 9 + 7
m = max(a) + 2
dp = [0] * m
dp[0] = 1
for i in range(n):
	r_col = get_prime(a[i])
	for j in r_col:
		dp[j] += dp[j - 1]
print((sum(dp) - 1) % M)


import os
import sys
from io import BytesIO, IOBase
import math
mod = int(1000000000.0 + 7)

def getfactor(num):
	boss = set()
	for x in range(1, math.floor(math.sqrt(num)) + 2):
		if num % x == 0:
			boss.add(x)
			boss.add(num // x)
	return list(boss)

def main():
	n = int(input())
	a = list(map(int, input().split(' ')))
	if n == 1:
		print(1)
		return
	dp = [0 for x in range(1111111)]
	dp[0] = 1
	for x in range(0, n):
		boss = getfactor(a[x])
		boss.sort(reverse=True)
		for x in range(len(boss)):
			dp[boss[x]] += dp[boss[x] - 1]
			dp[boss[x]] %= mod
	ans = 0
	for x in range(1, n + 1):
		ans = (ans % mod + dp[x] % mod) % mod
	print(ans)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import math
pri = pow(10, 9) + 7

def factors(x):
	ans = []
	for i in range(1, int(math.sqrt(x)) + 1):
		if x % i == 0 and i != x // i:
			ans.append(i)
			ans.append(x // i)
		elif x % i == 0:
			ans.append(i)
	return ans
a = int(input())
z = list(map(int, input().split()))
from collections import *
al = defaultdict(int)
total = 0
al[0] = 1
for i in range(len(z)):
	if i == 0:
		al[1] += 1
		total = 1
	else:
		m = factors(z[i])
		m.sort(reverse=True)
		for x in range(len(m)):
			if m[x] > i + 1:
				continue
			total += al[m[x] - 1]
			al[m[x]] += al[m[x] - 1]
			al[m[x]] %= pri
			total %= pri
print(total)


import sys
import math
from collections import defaultdict
mod = 10 ** 9 + 7

def get_factors(num, factors):
	if factors[num] != []:
		return
	for i in range(1, int(math.sqrt(num) + 1)):
		if num % i == 0:
			factors[num].append(i)
			if num // i != i:
				factors[num].append(num // i)
n = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))
factors = defaultdict(list)
dp = defaultdict(int)
dp[0] = 1
for i in range(n):
	get_factors(arr[i], factors)
	m = len(factors[arr[i]])
	for j in range(m - 1, -1, -1):
		if factors[arr[i]][j] <= i + 1:
			dp[factors[arr[i]][j]] += dp[factors[arr[i]][j] - 1]
			dp[factors[arr[i]][j]] %= mod
ans = 0
for i in dp:
	ans += dp[i]
	ans %= mod
ans -= 1
ans %= mod
print(ans)


import math
n = int(input())
arr = list(map(int, input().split()))
dp = [0] * (n + 1)
dp[1] = 1
dp[0] = 1
mod = 10 ** 9 + 7
for i in range(2, n + 1):
	update = []
	for d in range(1, int(math.sqrt(arr[i - 1])) + 1):
		if arr[i - 1] % d == 0:
			update.append(d)
			if d * d != arr[i - 1]:
				update.append(arr[i - 1] // d)
	update.sort()
	update.reverse()
	for j in update:
		if j <= n:
			dp[j] += dp[j - 1]
			dp[j] %= mod
total = -1
for val in dp:
	total = (total + val) % mod
print(total)


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(1000000000.0 + 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()


x = int(input())
s = list(map(int, input().split()))
ln = max(s) + 1
siv = [[] for n in range(ln)]
for n in range(1, ln):
	for k in range(n, ln, n):
		siv[k].append(n)
mod = int(1000000000.0 + 7)
dp = [0] * ln
dp[0] = 1
tem = [0] * ln
res = 0
for n in s:
	cur = n
	for k in siv[cur]:
		res += dp[k - 1]
		res %= mod
		tem[k - 1] += dp[k - 1]
		tem[k - 1] %= mod
	for k in siv[cur]:
		dp[k] = tem[k - 1]
		dp[k] %= mod
print(res)