問題文

マコトくんは以下の問題を考えました。

An Interval Scheduling Problem

N 個の区間 [L_i,R_i] が与えられます。以下の条件を満たすように選択できる区間の個数の最大値を求めてください。

• 選択した区間のうちどの二つも、共通部分を持たない。

制約

• 数列 L と R の中には、 1 から 2N までの整数がちょうど 1 回ずつ出現する
• L_i < R_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 点が与えられる。

入力例1

2

出力例1

8

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 となります。

入力例 2

4

出力例 2

4944

このテストケースは 10 点分の部分点に含まれます。

入力例 3

2021

出力例 3

383310824

このテストケースは 30 点分の部分点に含まれます。

入力例 4

100000

出力例 4

143469183

このテストケースは部分点に含まれません。