小圆想考入“新西伯利亚国立大学”,但在入学考试中她遇到了一个非常困难的任务:
给定一个整数$$$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$$$