配点 : $500$ 点

問題文

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

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

制約

• $1 \leq N \leq 500$

入力

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

$N$

出力

答えを出力せよ．

2

8

例えば，以下のような書き込み方は条件を満たします．

13
42

この場合，左上のマスは左下のマスに書かれている数より小さい数が書かれているので， $1$ つ目の条件を満たします．ただし，$2$ つ目の条件は満たしません．

5

704332752

100

927703658