可排序排列计数

题目描述

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

如果存在一个整数 $x \ge 2$，满足以下性质，则称这个排列是可排序的：删除排列中所有位置能被 $x$ 整除的元素后，剩下的数组严格递增。也就是说，删除位置为 $x, 2x, 3x, \ldots$ 且不超过 $n$ 的元素，保持剩余元素的相对顺序不变，得到的数组必须严格递增。位置从 $1$ 开始编号。

统计大小为 $n$ 的可排序排列的数量。答案可能很大，请输出对 $998244353$ 取模后的结果。

输入格式

只有一行，包含一个整数 $n$（$1 \le n \le 2 \times 10^5$）——排列的大小。

输出格式

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

样例输入

样例输入 1

1

样例输入 2

3

样例输入 3

6

样例输出

样例输出 1

1

样例输出 2

4

样例输出 3

135

样例解释

第一个样例中，$n=1$，唯一的排列是 $[1]$。取 $x=2$，位置 $2$ 不存在，因此不会删除任何元素，剩余数组仍为 $[1]$，它严格递增，所以该排列可排序。因此答案为 $1$。

数据范围

$1 \le n \le 2 \times 10^5$。答案对 $998244353$ 取模。时间限制为 $8$ 秒，内存限制为 $1024$ MB。