题目描述

$(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$ で割ったあまりを求めてください。

输入格式

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

$N$

输出格式

答えを出力せよ。

题目大意

给定 $n$ ，输 $2⋅n$ 的所有排列中，将其分成两个大小为 $n$ 的子序列 $A$ , $B$ ，使得 $H_n = \sum_{i = 1}^{n} \ A_i \cdot \ B_{i}$ 为最大值的方案数。

2

16

10000

391163238

提示

制約

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

Sample Explanation 1

考えられる順列 $24$ 通りの中で、スコアの最大値 $M$ は $14$ です。スコアが $14$ となる順列は $16$ 通りあります。 例えば、順列 $(1,2,3,4)$ は $A=(1,3),\ B=(2,4)$ と分割することで、$\sum\ _{i=1}^{N}A_i\ B_i\ =\ 14$ となります。

Sample Explanation 2

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