You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

时空限制

2S/1024M

题目描述

求 $\sum_{i=1}^N\sum_{j=1}^N\gcd(i,j)\mod 998244353$。

格式

输入格式

第一行包含一个整数 $N$，含义与题目描述相同。

输出格式

输出一个整数表示答案。对 $998244353$ 取模。

样例

样例输入 #1

6

样例输出 #1

61

样例输入 #2

4999

样例输出 #2

135537352

样例输入 #3

49999999

样例输出 #3

182045492

数据规模

对于 $30\%$ 的数据，$N\leq 5000$。

对于 $60\%$ 的数据，$N\leq 10^6$。

对于 $100\%$ 的数据，$1\leq N\leq 5\times 10^7$。