网格计数

时间限制：2s
空间限制：1024MB

题目描述

在一个 $N\times N$ 的方格中填入 $1$ 到 $N^2$ 的整数，每个整数恰好出现一次。

如果每个格子都至少满足下面两个条件之一，则称这种填法是合法的：

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

请计算合法填法的数量，并对 $998244353$ 取模。

输入格式

输入一行一个整数 $N$。

输出格式

输出一个整数，表示答案。

样例输入 1

2

样例输出 1

8

样例输入 2

5

样例输出 2

704332752

样例输入 3

100

样例输出 3

927703658

数据范围

对于所有数据，$1\le N\le 500$。