AT_utpc2021_j Do you like Interval Scheduling Problems?

[problemUrl]: https://atcoder.jp/contests/utpc2021/tasks/utpc2021_j マコトくんは以下の問題を考えました。

入力は以下の形式で標準入力から与えられる。 > $ 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 このテストケースは部分点に含まれません。