AT_agc076_a.[AGC076A] Hamming-Distant Arrays

给定一个整数 $N$。对于长度为 $N^2$ 的整数序列 $a$ 和 $b$，它们的每个元素都是 $1$ 到 $N$ 之间的整数，我们定义它们的距离 $d(a,b)$ 如下：

• $d(a,b)=$“满足 $a_i \neq b_i$ 的下标 $i$（$1 \leq i \leq N^2$）的个数”。

现在，你需要构造 $N$ 个长度为 $N^2$ 的整数序列，每个元素都是 $1$ 到 $N$ 之间的整数，记为 $x_1, x_2, \cdots, x_N$（序列顺序视为有区分）。请计算满足下列条件的 $(x_1, x_2, \cdots, x_N)$ 的方案数，答案对 $998244353$ 取模。

• 对于任意长度为 $N^2$ 的整数序列 $y$，$y$ 的每个元素均为 $1$ 到 $N$ 之间的整数，必定存在某个 $1 \leq i \leq N$，使得 $d(x_i, y) \geq N^2-N$。

输入从标准输入读取，格式如下：

$N$

输出答案。

样例解释 1

例如，$(x_1,x_2)=((1,1,2,2),(1,2,1,2))$ 不满足条件，因为如果 $y=(1,1,1,2)$，那么 $d(x_1,y)=1, d(x_2,y)=1$。

另一方面，$(x_1,x_2)=((1,1,1,1),(2,2,2,2))$ 满足条件。

满足条件的 $(x_1, x_2)$ 一共有 $80$ 种。

数据范围

• $1 \leq N \leq 50$
• 所有输入值都是整数。

由 ChatGPT 5 翻译