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 自动生成**

入力は以下の形式で標準入力から与えられる。 > $ N $

答えを一行に出力せよ。

### An Interval Scheduling Problem > $ N $ 個の区間 $ [L_i,R_i] $ が与えられます。以下の条件を満たすように選択できる区間の個数の最大値を求めてください。 > > - 選択した区間のうちどの二つも、共通部分を持たない。 > > #### 制約 > > - 数列 $ L $ と $ R $ の中には、 $ 1 $ から $ 2N $ までの整数がちょうど $ 1 $ 回ずつ出現する > - $ L_i\ (\ 1\ \leq\ i\ \leq\ N) $ - - - - - - この問題は典型的すぎたので、数え上げが大好きなテルオくんは以下のように問題を作り替えました。 - - - - - - ### Interval Scheduling Problems > 整数 $ N $ が与えられます。**An Interval Scheduling Problem** の制約を満たす入力全てに対する解の総和を $ 998244353 $ で割った余りを出力してください。 - - - - - - **Interval Scheduling Problems** を解いてください。 ### 制約 - $ 1\ \leq\ N\ \leq\ 2\times\ 10^5 $ ### 部分点 この問題には複数の部分点が設定されている。 - $ 1\ \le\ N\ \le\ 50 $ を満たすデータセットに正解した場合は $ 10 $ 点が与えられる。 - $ 1\ \le\ N\ \le\ 3000 $ を満たすデータセットに正解した場合は $ 30 $ 点が与えられる。 ### Sample Explanation 1 \*\*An Interval Scheduling Problem\*\* の入力として考えられるものは、以下の $ 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 $ 通りの入力に対する \*\*An Interval Scheduling Problem\*\* の答えは $ 1,1,2,1,1,2 $ なので、\*\*Interval Scheduling Problems\*\* の答えは $ 1+1+2+1+1+2 $ を $ 998244353 $ で割った余りの $ 8 $ となります。 ### Sample Explanation 2 このテストケースは $ 10 $ 点分の部分点に含まれます。 ### Sample Explanation 3 このテストケースは $ 30 $ 点分の部分点に含まれます。 ### Sample Explanation 4 このテストケースは部分点に含まれません。