Анонсирован VK Cup 2018! Регистрация уже идет! Приглашаем ознакомиться с информацией о Чемпионате на его странице. ×

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

Зима пришла на Севере и белые ходоки близко. Армия Джона Сноу состоит из n солдат. Пока остальная часть мира сражается за Железный трон, он собирается подготовиться к атаке белых ходоков.

Он придумал метод оценки силы своей армии. Пусть сила i-го солдата ai. Для некоторого k он называет i1, i2, ..., ik кланом, если i1 < i2 < i3 < ... < ik и gcd(ai1, ai2, ..., aik) > 1. Он считает силой этого клана k·gcd(ai1, ai2, ..., aik). Тогда сила армии равна сумме сил всех кланов в армии.

Ваша задача - найти силу его армии. Так как это число может быть очень большим, выведите его по модулю 1000000007 (109 + 7).

Наибольшим общим делителем (greatest common divisor, gcd) последовательности целых чисел называется наибольшее целое число такое, что каждый элемент последовательности делится на это число.

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

Первая строка содержит целое число n (1 ≤ n ≤ 200000) — размер армии.

Вторая строка содержит n целых чисел a1, a2, ..., an (1 ≤ ai ≤ 1000000) — силы солдат в армии.

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

Выведите одно число — силу армии Джона Сноу по модулю 1000000007 (109 + 7).

Примеры
Входные данные
3
3 3 1
Выходные данные
12
Входные данные
4
2 3 4 6
Выходные данные
39
Примечание

В первом примере кланы — {1}, {2}, {1, 2}, так что ответ 1·3 + 1·3 + 2·3 = 12