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

Эти числа очень заинтриговали Вадима, и он решил посчитать обратные к НОДу для всех пар чисел от 1 до N. К сожалению, это очень долгое занятие, поэтому Вадим просит вас помочь найти среднее арифметическое всех этих значений.

В единственной строке вводится целое число N (1 ≤ N ≤ 10⁷).

Выведите ответ на задачу по модулю 10⁹ + 7. То есть если ваш ответ представляет из себя несократимую дробь p/q, то выведите такое целое x, что 0 ≤ x ≤ 10⁹ + 6 и p ≡ q · x   (mod  10⁹ + 7).

В первом примере есть три НОДа: НОД(1, 1) = 1, НОД(1, 2) = 1, НОД(2, 2) = 2. Среднее арифметическое обратных к этим НОДам равно: