CF1528B Kavi on Pairing Duty
题目描述
Kavi 有 $2n$ 个点，这些点都位于 $OX$ 轴上，第 $i$ 个点的位置为 $x = i$。
Kavi 考虑将这 $2n$ 个点分成 $n$ 对的所有方式。在这些方式中，他对“好配对”感兴趣，定义如下：
考虑 $n$ 条线段，每条线段的两个端点分别是每一对中的两个点。如果对于任意两条不同的线段 $A$ 和 $B$，至少满足以下条件之一，则该配对被称为“好配对”：
- 其中一条线段完全包含在另一条线段内部。
- $A$ 和 $B$ 的长度相等。
请看以下示例：
 $A$ 是一个好配对，因为红色线段完全包含在蓝色线段内部。
$B$ 是一个好配对，因为红色和蓝色线段长度相等。
$C$ 不是好配对，因为红色和蓝色线段既不互相包含，也长度不相等。
Kavi 想知道好配对的数量。由于答案可能很大，请输出对 $998244353$ 取模后的结果。
如果某两个点在某种配对中被分到同一对，而在另一种配对中被分到不同的对，则这两种配对被认为是不同的。
输入格式
输入包含一行，一个整数 $n$，满足 $1 \le n \le 10^6$。
输出格式
输出一个整数，表示好配对的数量，对 $998244353$ 取模。
说明/提示
对于第二个样例，好配对如下：
对于第三个样例，好配对如下：
由 ChatGPT 4.1 翻译