题目描述

$N\ \times\ N$ のマス目の各マスに $1$ から $N^2$ までの整数を $1$ つずつ書き込む方法であって， どのマスも以下の条件のうち少なくとも一方を満たすようなものの個数を $998244353$ で割ったあまりを求めてください．

• そのマスに書かれている数より大きい数が書かれているマスが同じ列に存在する．
• そのマスに書かれている数より小さい数が書かれているマスが同じ行に存在する．

输入格式

入力は以下の形式で標準入力から与えられる．

$N$

输出格式

答えを出力せよ．

题目大意

统计将 $1 \sim N^2$ 共 $N^2$ 个整数填入 $N \times N$ 的棋盘并满足对于每个格子均满足以下至少一个条件的方案数，对 $998244353$ 取模：

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

2

8

5

704332752

100

927703658

提示

制約

• $1\ \leq\ N\ \leq\ 500$

Sample Explanation 1

例えば，以下のような書き込み方は条件を満たします． 13 42 この場合，左上のマスは左下のマスに書かれている数より小さい数が書かれているので， $1$ つ目の条件を満たします．ただし，$2$ つ目の条件は満たしません．