C. Делимость
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан массив целых чисел $$$a_1, a_2, \ldots, a_n$$$.

Массив $$$b$$$ называется подпоследовательностью $$$a$$$ если можно удалить некоторые элементы $$$a$$$, чтобы остался массив $$$b$$$.

Массив $$$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$$$.

Примеры
Входные данные
2
1 2
Выходные данные
3
Входные данные
5
2 2 1 22 14
Выходные данные
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\}$$$.

Обратите внимание, что некоторые подпоследовательности упомянуты несколько раз, так как они входят в исходный массив несколько раз.