Назовём непустую последовательность натуральных чисел a1, a2... ak взаимно простой, если наибольший общий делитель всех элементов последовательности равен 1.
Дан массив a, состоящий из n натуральных чисел. Найдите количество его взаимно простых подпоследовательностей. Так как ответ может быть очень большим, выведите его по модулю 109 + 7.
Обратите внимание: две подпоследовательности считаются различными, если различны выбранные индексы. К примеру, в массиве [1, 1] 3 различных подпоследовательности: [1], [1] и [1, 1].
Выходные данные
Выведите единственное число — количество взаимно простых подпоследовательностей a по модулю 109 + 7.
Примечание
В первом примере взаимно простыми являются следующие подпоследовательности:
- 1
- 1, 2
- 1, 3
- 1, 2, 3
- 2, 3
Во втором примере все подпоследовательности являются взаимно простыми.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1 2 3
|
5
|
|
2
|
4
1 1 1 1
|
15
|
|
3
|
7
1 3 5 15 3 105 35
|
100
|