题目描述

在一个 $N \times N$ 的方格中，每个格子填入 $1$ 到 $N^2$ 的整数，每个数恰好出现一次。请计算有多少种填数方式，使得每个格子都至少满足以下两个条件之一，将答案对 $998244353$ 取模。

• 在同一列中，存在一个格子，其数比当前格子的数大。
• 在同一行中，存在一个格子，其数比当前格子的数小。

输入格式

输入通过标准输入给出，格式如下：

$N$

输出格式

输出答案。

样例 1

输入

2

输出

8

样例 2

输入

5

输出

704332752

样例 3

输入

100

输出

927703658

说明/提示

限制

• $1 \leq N \leq 500$

样例说明 1

例如，以下的填数方式满足条件：

1 3
4 2

在这个例子中，左上角的格子，因为同一列下方有比它大的数，所以满足第一个条件。注意，第二个条件没有被满足。

由 ChatGPT 4.1 翻译