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.