配点 : $600$ 点

問題文

$(1,2,\ldots,2N)$ の順列 $P=(P_1,P_2,\ldots,P_{2N})$ に対し、スコアを以下で定義します。

$$P$$$$N$$$$ A = (A_1,A_2,\ldots,A_N),B = (B_1,B_2,\ldots,B_N)$$$$\displaystyle\sum_{i=1}^{N}A_i B_i$$$(1,2,\ldots,2N)$ の順列全てについてスコアを計算し、それらの最大値を $M$ とします。 $(1,2,\ldots,2N)$ の順列のうち、スコアが $M$ であるものの個数を $998244353$ で割ったあまりを求めてください。 $$

制約

• $1 \leq N \leq 2\times 10^5$
• 入力は全て整数

入力

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

$N$

出力

答えを出力せよ。

2

16

考えられる順列 $24$ 通りの中で、スコアの最大値 $M$ は $14$ です。スコアが $14$ となる順列は $16$ 通りあります。

例えば、順列 $(1,2,3,4)$ は $A=(1,3), B=(2,4)$ と分割することで、$\sum _{i=1}^{N}A_i B_i = 14$ となります。

10000

391163238

$998244353$ で割ったあまりを答えてください。