公倍树

题目描述

某图上有 $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$