F. Взаимно простые подпоследовательности
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Назовём непустую последовательность натуральных чисел a1, a2... ak взаимно простой, если наибольший общий делитель всех элементов последовательности равен 1.

Дан массив a, состоящий из n натуральных чисел. Найдите количество его взаимно простых подпоследовательностей. Так как ответ может быть очень большим, выведите его по модулю 109 + 7.

Обратите внимание: две подпоследовательности считаются различными, если различны выбранные индексы. К примеру, в массиве [1, 1] 3 различных подпоследовательности: [1], [1] и [1, 1].

Входные данные

В первой строке записано единственное натуральное число n (1 ≤ n ≤ 100000).

Во второй строке записаны n натуральных чисел a1, a2... an (1 ≤ ai ≤ 100000).

Выходные данные

Выведите единственное число — количество взаимно простых подпоследовательностей a по модулю 109 + 7.

Примеры
Входные данные
3
1 2 3
Выходные данные
5
Входные данные
4
1 1 1 1
Выходные данные
15
Входные данные
7
1 3 5 15 3 105 35
Выходные данные
100
Примечание

В первом примере взаимно простыми являются следующие подпоследовательности:

  1. 1
  2. 1, 2
  3. 1, 3
  4. 1, 2, 3
  5. 2, 3

Во втором примере все подпоследовательности являются взаимно простыми.