题目描述

对于 $(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$。请你求出得分等于 $M$ 的排列个数，并对 $998244353$ 取模后输出。

输入格式

输入为一行，包含一个整数 $N$。

输出格式

输出一个整数，表示得分等于最大值 $M$ 的排列个数对 $998244353$ 取模的结果。

样例 1

输入

2

输出

16

样例 2

输入

10000

输出

391163238

说明/提示

限制

• $1\leq N\leq 2\times 10^5$
• 输入均为整数

样例解释 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$。

样例解释 2

请输出对 $998244353$ 取模的答案。

由 ChatGPT 4.1 翻译