Зима пришла на Севере и белые ходоки близко. Армия Джона Сноу состоит из 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
| Codeforces Round 428 (Div. 2) |
|---|
| Закончено |
