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.

B. 博弈论

题目描述

定义对于数对 $(a,b)$ 的一次变换为 $(\min(a,b),\max(a,b)-\min(a,b))$。记 $f(x,y)$ 为数对 $(x,y)$ 变换的最少次数，直到 $\min(x,y)=0$。现在给定 $n$ 求 $\sum_{1\leq i,j\leq n}f(i,j)$。

答案对 $998244353$ 取模。

输入格式

一行一个正整数 $n$。

输出格式

一行一个整数，表示答案对 $998244353$ 取模的值。

样例 #1

样例输入 #1

5

样例输入 #1

77

样例 #2

样例输入 #2

199977

样例输出 #2

983457886

数据范围

对于所有数据，保证 $1\le n\le 2\times10^7$。