Description

给定一个大小为 $N \times N$ 的矩阵， 你可以往里面填入$1$ ~ $N \times N$ 的元素，求有多少种填法且对于每个格子均使得下列条件至少有一个成立：

• 该格子不是所处的列的最大值
• 该格子不是所处的行的最小值

答案对 $998244353$ 取模

Format

Input

一行一个整数 $N$

$1 \leq N \leq 500$

Output

一行一个整数

Samples

2

8

提示

以下是其中一种填充方式

13
42

在这个样例中左上角的数 $1$ 满足第一个条件，但不满足第二个条件。