Мадока хочет поступить в «Новосибирский Государственный Университет», но на вступительном экзамене ей попалась очень сложная задача:
Дано число \(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\).
Решите эту задачу за Мадоку и помогите ей поступить в лучший университет!
Выходные данные
Выведите ровно одно число — \(\sum{\operatorname{lcm}(c, \gcd(a, b))}\). Так как ответ может быть очень большим, то выведите его по модулю \(10^9 + 7\).
Примечание
В первом примере есть только одна подходящая тройка \((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\)