C 拼图（jigsaw）
TIME:1S
Memory:512M
【问题描述】
对于正整数对 $(a,b)$，定义一次操作将其变换为 $(\min(a,b),\max(a,b)-\min(a,b))$。
设 $f(a,b)$ 为最小的操作次数，使得某一个数变为 $0$。
给定正整数 $N$，求 $\sum_{i=1}^N\sum_{j=1}^Nf(i,j)$，对 $998244353$ 取模。
【输入格式】
从文件 $jigsaw.in$ 中读入数据。
第一行包含一个整数 $N$。
【输出格式】
输出到文件 $jigsaw.out$ 中。
输出一行一个整数，表示答案。
【样例输入1】
5【样例输出1】
77【样例2】
见选手目录下的 $jigsaw/jigsaw2.in$ 与 $jigsaw/jigsaw2.ans$。
【样例3】
见选手目录下的 $jigsaw/jigsaw3.in$ 与 $jigsaw/jigsaw3.ans$。
【样例4】
见选手目录下的 $jigsaw/jigsaw4.in$ 与 $jigsaw/jigsaw4.ans$。
【数据范围及约定】
对于所有数据，保证：$1\le N\le 2\times10^7$。
| 测试点编号 | $N\le$ |
|---|---|
| $1$ | $100$ |
| $2$ | $300$ |
| $3$ | $800$ |
| $4$ | $1500$ |
| $5$ | $3000$ |
| $6$ | $8000$ |
| $7,8,9,10,11,12$ | $2\times 10^5$ |
| $13,14,15,16,17,18$ | $2\times 10^6$ |
| $19,20,21,22,23,24,25$ | $2\times 10^7$ |