Зима пришла на Севере и белые ходоки близко. Армия Джона Сноу состоит из 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) последовательности целых чисел называется наибольшее целое число такое, что каждый элемент последовательности делится на это число.
Примечание
В первом примере кланы — {1}, {2}, {1, 2}, так что ответ 1·3 + 1·3 + 2·3 = 12