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.

Input

Input is given from Standard Input in the following format:
N

Output

Print the answer.

Constraints

• $1 \leq N \leq 500$

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

见题面 Input 部分

见题面 Output 部分