Вам дан массив целых чисел \(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\) различных подпоследовательностей (не считая пустую).
Выходные данные
Выведите одно целое число — количество хороших подпоследовательностей по модулю \(10^9 + 7\).
Примечание
В первом примере все три непустые подпоследовательности являются хорошими: \(\{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\}\).
Обратите внимание, что некоторые подпоследовательности упомянуты несколько раз, так как они входят в исходный массив несколько раз.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
1 2
|
3
|
|
2
|
5
2 2 1 22 14
|
13
|