CF2260G.Sortable Permutations

A permutation of size $n$ is an array of length $n$ in which every integer from $1$ to $n$ appears exactly once.

We call a permutation sortable if there exists an integer $x\ge 2$ such that the following property holds: if we remove from the permutation all elements at positions divisible by $x$, then the remaining array is strictly increasing. In other words, the elements at positions $x,2x,3x,\ldots$, not exceeding $n$, are removed, the order of the remaining elements is unchanged, and the resulting array must be strictly increasing. Positions are numbered starting from $1$.

Count the number of sortable permutations of size $n$. Since the answer may be very large, output it modulo $998244353$.

大小为 $n$ 的一个排列是指长度为 $n$ 的数组，其中 $1$ 到 $n$ 的每个整数恰好出现一次。

我们称一个排列是可排序的（sortable），如果存在某个整数 $x \ge 2$，使得如下性质成立：若从该排列中删去所有位置编号能被 $x$ 整除的元素，则剩余数组严格递增。换言之，删去位置编号为 $x, 2x, 3x, \ldots$（且不超过 $n$）的所有元素，其余元素保持原有顺序，所得数组必须严格递增。位置编号从 $1$ 开始。

求大小为 $n$ 的可排序排列的个数。由于答案可能非常大，请对 $998244353$ 取模后输出。

The only line contains one integer $n$ ($1\le n\le 2\cdot10^5$) — the size of the permutation.

唯一的一行包含一个整数 $n$（$1\le n\le 2\cdot10^5$）—— 排列的大小。

Output one integer — the number of sortable permutations of size $n$, taken modulo $998244353$.

输出一个整数——大小为 $n$ 的可排序排列的个数，对 $998244353$ 取模。

In the first example, the only permutation is $[1]$. For $x=2$, nothing is removed, and the sequence is already sorted.

In the second example, the sortable permutations are $[1,2,3]$, $[1,3,2]$, $[2,1,3]$, and $[2,3,1]$. For example, for the permutation $[2,1,3]$, $x=2$ works: after removing the second element, the sequence $[2,3]$ remains.

In the third example, one of the sortable permutations is $[1,3,6,4,5,2]$. For $x=3$, the elements at positions $3$ and $6$ are removed, after which the strictly increasing sequence $[1,3,4,5]$ remains.

在第一个例子中，唯一的排列是 $[1]$。当 $x=2$ 时，不删除任何元素，此时序列本身已为升序。

在第二个例子中，可排序的排列有 $[1,2,3]$、$[1,3,2]$、$[2,1,3]$ 和 $[2,3,1]$。例如，对排列 $[2,1,3]$，取 $x=2$ 是可行的：删除第 $2$ 个元素后，剩余序列为 $[2,3]$。

在第三个例子中，一个可排序的排列是 $[1,3,6,4,5,2]$。当 $x=3$ 时，位置为 $3$ 和 $6$ 的元素被删除，之后剩余严格递增序列 $[1,3,4,5]$。