E. Подарок для филателиста Виталика
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У филателиста Виталика сегодня день рождения!

Как постоянному клиенту магазина почтовых марок «Робин Бобин», руководство магазина решило сделать ему подарок.

Виталик хочет купить одну марку, а магазин, в свою очередь, подарит ему некоторый непустой набор из оставшихся марок, такой, что наибольший общий делитель (НОД) цен подаренных марок больше единицы. Если НОД цен купленной марки и цен марок из подаренного набора окажется равен 1, то Виталик уйдет из магазина абсолютно счастливым.

Руководство магазина просит вас посчитать количество различных ситуаций, при которых Виталик уйдет из магазина абсолютно счастливым. Так как искомое количество ситуаций может оказаться очень большим, вам требуется найти остаток от деления этого количества на число 109 + 7. Ситуации считаются различными, если различаются марки, купленные Виталиком, или один из подарков содержит марку, которую не содержит другой.

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

В первой строке входных данных содержится целое число n (2 ≤ n ≤ 5·105) — количество различных марок, имеющихся в продаже в магазине «Робин Бобин». Вторая строка содержит последовательность целых чисел a1, a2, ..., an (2 ≤ ai ≤ 107), где ai — цена i-й марки.

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

Выведите одно целое число — остаток от деления искомого количества ситуаций на число 109 + 7.

Примеры
Входные данные
3
2 3 2
Выходные данные
5
Входные данные
2
9 6
Выходные данные
0
Примечание

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

  • Виталик покупает 1-ю марку, магазин дарит 2-ю марку;
  • Виталик покупает 3-ю марку, магазин дарит 2-ю марку;
  • Виталик покупает 2-ю марку, магазин дарит 1-ю марку;
  • Виталик покупает 2-ю марку, магазин дарит 3-ю марку;
  • Виталик покупает 2-ю марку, магазин дарит 1-ю и 3-ю марки.