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

Он придумал метод оценки силы своей армии. Пусть сила i-го солдата a_i. Для некоторого k он называет i₁, i₂, ..., i_k кланом, если i₁ < i₂ < i₃ < ... < i_k и gcd(a_i1, a_i2, ..., a_ik) > 1. Он считает силой этого клана k·gcd(a_i1, a_i2, ..., a_ik). Тогда сила армии равна сумме сил всех кланов в армии.

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

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