問題文

ある池でマラソン大会が開催されます。池は円形で、池の外周に沿って時計回りに等間隔に 1, 2,\ldots, 2N の印がつけられています。マラソン大会の参加者は 2N 人いて、そのうち N 人が赤色の帽子を、残りの N 人が白色の帽子を被っています。

マラソン大会は以下のように実行されます。

• 2N 個ある印それぞれについて、ちょうど 1 人がその位置につく。
• 印 1 が付けられた位置にいる人がバトンを持って時計回りに走り始める。
• i 番目 (1 \le i \le 2N - 1) に走る人は、最初に自分と異なる色の帽子を被っている人のいる位置に到達するまで走り続ける。到達したら、その相手にバトンを渡して池から離れる。バトンを渡された人は、時計回りに走り始める。
• 2N 番目に走る人は、印 1 が付けられた位置まで走りマラソン大会を終了する。

池 1 周の長さを 1 とすると、2N 人が走る距離の合計は整数になり、これを L とします。

ありうる 2N 人の配置は (2N)! 通りありますが、その全てについての L の総和を 998244353 で割った余りを求めてください。

制約

• 入力は全て整数
• 1 \leq N \leq 10^6

入力例 1

1

出力例 1

2

ありうる配置は 2 通りありますが、いずれの場合も L=1 となります。

入力例 2

2

出力例 2

40

参加者の被っている帽子の色が印 1 が付けられた位置から順に

• 赤赤白白のときは L=2
• 赤白赤白のときは L=1
• 赤白白赤のときは L=2
• 白赤赤白のときは L=2
• 白赤白赤のときは L=1
• 白白赤赤のときは L=2

となります。それぞれに 4 通りの配置があるので、ありうる 24 通りの配置全てについての L の総和は (2 + 1 + 2 + 2 + 1 + 2) \times 4 = 40 です。

入力例 3

3

出力例 3

1656

入力例 4

4

出力例 4

112896

入力例 5

5

出力例 5

11750400