/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
N \times N のマス目の各マスに 1 から N^2 までの整数を 1 つずつ書き込む方法であって， どのマスも以下の条件のうち少なくとも一方を満たすようなものの個数を 998244353 で割ったあまりを求めてください．
- そのマスに書かれている数より大きい数が書かれているマスが同じ列に存在する．
- そのマスに書かれている数より小さい数が書かれているマスが同じ行に存在する．
制約
- 1 \leq N \leq 500
入力
入力は以下の形式で標準入力から与えられる．
N
出力
答えを出力せよ．
入力例 1
2
出力例 1
8
例えば，以下のような書き込み方は条件を満たします．
13 42
この場合，左上のマスは左下のマスに書かれている数より小さい数が書かれているので， 1 つ目の条件を満たします．ただし，2 つ目の条件は満たしません．
入力例 2
5
出力例 2
704332752
入力例 3
100
出力例 3
927703658
Score : 500 points
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.
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