问题描述

对于排列 $P=(P_1,P_2,\\ldots,P_{2N})$ $(1,2,\\ldots,2N)$ 的得分定义如下：

考虑将 $P$ 分成两个（不一定连续的）子序列 $A = (A_1,A_2,\\ldots,A_N)$ 和 $B = (B_1,B_2,\\ldots,B_N)$。 在这种分割中，$P$ 的得分是 $\\displaystyle\\sum_{i=1}^{N}A_i B_i$ 的最大可能值。

令 $M$ 是所有 $(1,2,\\ldots,2N)$ 的排列的得分中的最大值。 找到得分为 $M$ 的排列的数量，取模 $998244353$。

约束条件

• $1 \\leq N \\leq 2\\times 10^5$
• 输入中的所有值都为整数。

输入

输入以以下格式从标准输入给出：

$N$

输出

输出答案。

示例输入1

2

示例输出1

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$。

示例输入2

10000

示例输出2

391163238

以模 $998244353$ 的形式打印计数。