AT_utpc2021_j.Do you like Interval Scheduling Problems?

马可托同学设计了以下问题：

区间调度问题

有 $N$ 个区间 $[L_i, R_i]$，请找出一组最大的区间选择方案，使得选中的任意两个区间没有重叠。

限制条件

• 数列 $L$ 和 $R$ 各包含从 $1$ 到 $2N$ 的所有整数，且每个整数恰好出现一次。
• $1 \leq i \leq N$

---

由于问题过于经典，热爱计数的特鲁奥同学将问题改为：

区间调度问题的总和

给定一个整数 $N$，计算所有满足 区间调度问题 限制条件的输入所对应答案的总和，然后输出这个和对 $998244353$ 的余数。

请解决 区间调度问题的总和。

输入格式

输入为一个整数：

$N$

输出格式

输出一行结果，需要是总和取模 $998244353$ 的结果。

数据范围

• $1 \leq N \leq 2 \times 10^5$

部分得分

本题提供多档部分分数：

• 若正确解答 $1 \leq N \leq 50$ 的数据集，可获得 $10$ 分。
• 若正确解答 $1 \leq N \leq 3000$ 的数据集，可获得 $30$ 分。

示例解释 1

对于 区间调度问题，可能的输入有以下 $6$ 种情况：

• $L = (1, 2),\ R = (3, 4)$
• $L = (1, 2),\ R = (4, 3)$
• $L = (1, 3),\ R = (2, 4)$
• $L = (2, 1),\ R = (3, 4)$
• $L = (2, 1),\ R = (4, 3)$
• $L = (3, 1),\ R = (4, 2)$

这 $6$ 种输入分别得到 区间调度问题 的答案为 $1, 1, 2, 1, 1, 2$。因此，区间调度问题的总和 的结果为：$(1 + 1 + 2 + 1 + 1 + 2) \mod 998244353 = 8$。

示例解释 2

这个测试案例属于 $10$ 分部分分数。

示例解释 3

这个测试案例属于 $30$ 分部分分数。

示例解释 4

这个测试案例不在部分分数范围内。

本翻译由 AI 自动生成