题目背景

这是 $CSP-J$ 模拟赛的 $T4$ 。

题目描述

某图上有 $n$ 个点分别标号为 $2,3...n + 1$

任意两点之间有一条边，边长为两条标号边的最小公倍数。

求该图最小生成树的边长总和模 $998244353$。

输入格式

输入一行。

一行输入一个整数 $n$ 。

输出格式

输出一行。

一行输出一个整数，为该图最小生成树的边长总和模$998244353$ 。

样例 #1

样例输入 #1

3

样例输出 #1

10

样例 #2

样例输入 #2

10

样例输出 #2

89

提示

样例解释】：

在第一个样例中，图上只有 $2,3,4$ 号点，最小生成树中 $2$ 号和 $3,4$ 号分别连一条边，权值分别为 $lcm(2,3)=6$ 和 $lcm(2,4)=4$。

数据范围】：

保证对于前 $30\%$ 的数据，$n \le 10$

保证对于前 $50\%$ 的数据, $n \le 10^5$

保证对于 $100\%$ 的数据, $1 < n \le 10^7$