题目描述

我们定义质数排序为将一个序列中的所有下标为质数的位置进行升序排序，其它位置上的数不变。

例如，对 $8, 7, 6, 5, 4, 3, 2, 1$ 进行质数排序会得到 $8, 2, 4, 5, 6, 3, 7, 1$。给定 $n$，求 $1 \sim n$ 的每个排列进行质数排序后的逆序对的数量的和。由于结果很大，你只需要输出答案对 $998244353$ 取模的结果即可。

输入格式

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

输出格式

输出一行包含一个整数表示答案。

3

6

提示

评测用例规模与约定

• 对于 $30\%$ 的评测用例，$n \leq 10$；
• 对于所有评测用例，$1 \leq n \leq 10^6$。