← 返回题目列表

Codeforces · 1717/E

E. 小圆和最好的大学

中文机器翻译题面 查看原题

小圆想考入“新西伯利亚国立大学”,但在入学考试中她遇到了一个非常困难的任务:

给定一个整数$$$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$$$ 取模。

示例

输入 #1

3

输出 #1

1

输入 #2

5

输出 #2

11

输入 #3

69228

输出 #3

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) + \运算符名称{lcm}(3, 1) = 1 + 2 + 1 + 2 + 2 + 3 = 11$$$