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

Мадока хочет поступить в «Новосибирский Государственный Университет», но на вступительном экзамене ей попалась очень сложная задача:

Дано число $$$n$$$, требуется вывести $$$\sum{\operatorname{lcm}(c, \gcd(a, b))}$$$, для всех троек положительных целых чисел $$$(a, b, c)$$$, где $$$a + b + c = n$$$.

В данной задаче $$$\gcd(x, y)$$$ обозначает наибольший общий делитель чисел $$$x$$$ и $$$y$$$, а $$$\operatorname{lcm}(x, y)$$$ обозначает наименьшее общее кратное чисел $$$x$$$ и $$$y$$$.

Решите эту задачу за Мадоку и помогите ей поступить в лучший университет!

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

Первая и единственная строка содержит единственное целое число $$$n$$$ ($$$3 \le n \le 10^5$$$).

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

Выведите ровно одно число — $$$\sum{\operatorname{lcm}(c, \gcd(a, b))}$$$. Так как ответ может быть очень большим, то выведите его по модулю $$$10^9 + 7$$$.

Примеры
Входные данные
3
Выходные данные
1
Входные данные
5
Выходные данные
11
Входные данные
69228
Выходные данные
778304278
Примечание

В первом примере есть только одна подходящая тройка $$$(1, 1, 1)$$$. Поэтому ответ равен $$$\operatorname{lcm}(1, \gcd(1, 1)) = \operatorname{lcm}(1, 1) = 1$$$.

Во втором примере, $$$\operatorname{lcm}(1, \gcd(3, 1)) + \operatorname{lcm}(1, \gcd(2, 2)) + \operatorname{lcm}(1, \gcd(1, 3)) + \operatorname{lcm}(2, \gcd(2, 1)) + \operatorname{lcm}(2, \gcd(1, 2)) + \operatorname{lcm}(3, \gcd(1, 1)) = \operatorname{lcm}(1, 1) + \operatorname{lcm}(1, 2) + \operatorname{lcm}(1, 1) + \operatorname{lcm}(2, 1) + \operatorname{lcm}(2, 1) + \operatorname{lcm}(3, 1) = 1 + 2 + 1 + 2 + 2 + 3 = 11$$$