题目背景

点我提交原题

题目描述

小円想要进入 新西伯利亚国立大学，但她在入学考试中遇到了一个非常棘手的问题：

给定一个整数 $n$ ，要求计算所有正整数 $(a, b, c)$ 的三元组 $\sum{\operatorname{lcm}(c, \gcd(a, b))}$ ，其中 $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$ 。