该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Problem 8F. Lcm and Gcd

时间限制：1s

空间限制：256MB

Description

给定一个整数 \(n\) ，对于所有正整数 \((a, b, c)\) 的三元组，计算 \(\sum{\operatorname{lcm}(c, \gcd(a, b))}\) ，其中 \(a + b + c = n\) 。

\(gcd(x,y)\) 表示 \(x\) 和 \(y\) 的 最大公因数 ，\(lcm(x, y)\) 表示 \(x\) 和 \(y\) 的 最小公倍数 。

Input Format

输入一行一个整数 \(n\) ， ( \(3 \le n \le 10^5\) )。

Output Format

输出一个整数 - \(\sum{\operatorname{lcm}(c, \gcd(a, b))}\) 。由于答案可能非常大，将答案对 \(998244353\) 取模。

Input Example #1：

3

Output Example #1：

1

Input Example #2：

5

Output Example #2：

11

Input Example #3：

69228

Output Example #3：

778304278

Note

在第一个示例中，只有一个合适的三元组 \((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\) 。