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.

时空限制

1S/512M

题目描述

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

格式

输入格式

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

输出格式

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

样例

样例输入 #1

6

样例输出 #1

55

样例输入 #2

999

样例输出 #2

1353015

样例输入 #3

2345678

样例输出 #3

527070827

数据规模

对于 $50\%$ 的数据，$N\leq 1000$。

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