201431: [AtCoder]ARC143 B - Counting Grids

Problem Statement

Find the number of ways, modulo $998244353$, to fill the squares of an $N \times N$ grid using each integer from $1$ to $N^2$ once so that every square satisfies at least one of the following conditions.

• In the same column, there is a square containing a number greater than that of the concerned square.
• In the same row, there is a square containing a number less than that of the concerned square.

Constraints

• $1 \leq N \leq 500$

Input

Input is given from Standard Input in the following format:

$N$

Output

Print the answer.

Sample Input 1

2

Sample Output 1

8

Here is one way to fill the grid to satisfy the requirement.

13
42

Here, the top-left square contains a number less than that of the bottom-left square, satisfying the first condition. It does not satisfy the second condition, however.

Sample Input 2

5

Sample Output 2

704332752

Sample Input 3

100

Sample Output 3

927703658