Split and Maximize

时间限制：2s
空间限制：512MB

题目描述

对 $1,2,\ldots,2N$ 的一个排列 $P=(P_1,P_2,\ldots,P_{2N})$，按下述方式定义它的得分：保持元素在 $P$ 中的相对顺序，将 $P$ 分成两个长度为 $N$ 的、不一定连续的子序列 $A=(A_1,\ldots,A_N)$ 与 $B=(B_1,\ldots,B_N)$，该划分的价值为 $\sum_{i=1}^{N}A_iB_i$；得分是所有划分的最大价值。

记所有 $1,2,\ldots,2N$ 的排列的得分最大值为 $M$。求得分等于 $M$ 的排列数量，答案对 $998244353$ 取模。

输入格式

输入一个整数 $N$。

输出格式

输出答案对 $998244353$ 取模的结果。

样例输入 1

2

样例输出 1

16

样例输入 2

10000

样例输出 2

391163238

数据范围

• $1\le N\le 2\times 10^5$。