该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

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

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

输入格式

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

$N$

输出格式

输出答案。

输入输出样例 #1

输入 #1

2

输出 #1

8

输入输出样例 #2

输入 #2

5

输出 #2

704332752

输入输出样例 #3

输入 #3

100

输出 #3

927703658

说明/提示

限制

• $1 \leq N \leq 500$

样例说明 1

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

1 3
4 2

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