随机棋盘(Easy Version)

题号：NC288082
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 本题为问题的简单版本，与困难版本的唯一区别在于 $n$ 的取值范围不同。

$\hspace{15pt}$ 这天，你试图解决下面这个问题：

〖引用开始〗

$\hspace{15pt}$ 在 $n$ 行 $n$ 列的棋盘上，一共有 $n \times n$ 个位置可以放置棋子。我们使用 $(i,j)$ 表示网格中从上往下数第 $i$ 行和从左往右数第 $j$ 列的单元格。你需要在棋盘中挑选 $n$ 个位置，每个位置上放置一枚象棋棋子中的“车”。求解摆放 $n$ 辆车，且任意两车都无法互相攻击到的方案数。两个方案视为相同，当且仅当这 $n$ 辆车在棋盘上的摆放位置完全相同。
$\hspace{15pt}$ 在象棋中，“车”的攻击范围为其所在的一整行以及一整列。为了方便描述，我们使用一个 $6 \times 6$ 的棋盘举例，用 $0$ 表示可以放置车的位置；用 $\color{purple}{\texttt{C}}$ 表示已经放在棋盘中的一辆“车”，其位于 $(3,4)$ 位置；用 $\texttt{X}$ 标记这辆车的攻击范围，如公式所示： $\begin{bmatrix}0 & 0 & 0& \texttt{X}&0 & 0\\0 & 0& 0& \texttt{X} & 0 & 0\\\texttt{X} & \texttt{X} & \texttt{X}&\color{purple}{\texttt{C}}&\texttt{X} & \texttt{X}\\0 & 0 & 0& \texttt{X}&0 & 0\\0 & 0 & 0& \texttt{X}&0 & 0\\0 & 0 & 0& \texttt{X}&0 & 0\end{bmatrix}$
$\hspace{15pt}$ 此时，如果要放置第二辆“车”，那么应该选择公式中为 $0$ 的位置，其余的位置都会被第一辆“车”的攻击到。

$\hspace{15pt}$ 在 $6 \times 6$ 的样例中，一个可行的摆放方案为： $\begin{bmatrix}0 & 0 & 0& \color{purple}{\texttt{C}}&0 & 0\\0 & 0& \color{purple}{\texttt{C}}& 0 & 0 & 0\\0 & \color{purple}{\texttt{C}} & 0& 0&0 & 0\\\color{purple}{\texttt{C}} & 0 & 0& 0&0 & 0\\0 & 0 & 0& 0&\color{purple}{\texttt{C}} & 0\\0 & 0 & 0& 0&0 & \color{purple}{\texttt{C}}\end{bmatrix}$

〖引用结束〗

$\hspace{15pt}$ 由于这个问题太简单，因此，你打算对棋盘进行一些变化。你将会书写一个程序，在棋盘上的随机位置生成禁止标记，这些位置上将不再能放置车。生成完毕后，再进行上述引用问题的求解。随机程序的逻辑为：
$\hspace{23pt}\bullet\,$ 生成一个长度为 $\left\lfloor\frac{n}{2}\right\rfloor$ 的排列 $p$ ，随后将其中的元素打乱。
$\hspace{23pt}\bullet\,$ 记打乱后的排列为 $\left\{p_1,p_2,\cdots,p_{\left\lfloor\frac{n}{2}\right\rfloor}\right\}$ ，取出第 $i$ 个元素 $p_i$ ，随后在棋盘中 $(2 \times p_i-1,2 \times i-1)$ 、 $(2 \times p_i,2 \times i-1)$ 、 $(2 \times p_i,2 \times i)$ 三个位置生成禁止标记。

$\hspace{15pt}$ 例如，在 $6 \times 6$ 的棋盘上，若得到的打乱后的排列为 $p=(2,3,1)$ ，使用 $1$ 表示有禁止标记的位置，棋盘的情况如公式所示： $\begin{bmatrix}0 & 0 & 0& 0&1 & 0\\0 & 0& 0& 0 & 1 & 1\\1 & 0 & 0& 0&0 & 0\\1 & 1 & 0& 0&0 & 0\\0 & 0 & 1& 0&0 & 0\\0 & 0 & 1& 1&0 & 0\end{bmatrix}$
$\hspace{15pt}$ 一个可行的摆放方案为： $\begin{bmatrix}0 & 0 & 0& \color{purple}{\texttt{C}}&1 & 0\\0 & 0& \color{purple}{\texttt{C}}& 0 & 1 & 1\\1 & \color{purple}{\texttt{C}} & 0& 0&0 & 0\\1 & 1 & 0& 0&0 & \color{purple}{\texttt{C}}\\0 & 0 & 1& 0&\color{purple}{\texttt{C}} & 0\\\color{purple}{\texttt{C}} & 0 & 1& 1&0 & 0\end{bmatrix}$

$\hspace{15pt}$ 现在，使用上述提到的随机程序生成棋盘，并进行上述问题的求解。求解最终的棋盘上摆放 $n$ 辆车、且任意两车都无法互相攻击到的方案数的期望。你需要将答案对 $998\,244\,353$ 取模后输出。

输入描述:

在一行上输入一个正整数  代表棋盘的边长，保证  是偶数。

输出描述:

输出一个整数，代表期望。 
可以证明答案可以表示为一个不可约分数 ，为了避免精度问题，请直接输出整数  作为答案，其中  ， 是满足  的整数。
更具体地，你需要找到一个整数  满足  对  取模等于 ，您可以查看样例解释得到更具体的说明。

示例1

输入

复制

输出

复制

说明

在这个样例中，使用随机程序生成得到的唯一的棋盘为 ，不存在任何摆放方案。

示例2

输入

复制

输出

复制