/ 
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 600 点
問題文
縦 N 行横 N 列のマス目があり、上から i 行目、左から j 列目のマスには整数のラベル a_{i,j} が付けられています。
いずれかのマスから始めて右または下に隣接するマスへの移動を 0 回以上繰り返すことで得られる経路のうち、始点と終点のラベルが同じものの個数を 998244353 で割った余りを求めてください。
なお、2 つの経路は通ったマス(始点・終点含む)の集合が異なる場合に区別します。
制約
- 1 \leq N \leq 400
- 1 \leq a_{i,j} \leq N^2
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N
a_{1,1} \ldots a_{1,N}
\vdots
a_{N,1} \ldots a_{N,N}
出力
答えを出力せよ。
入力例 1
2 1 3 3 1
出力例 1
6
条件を満たす経路は以下の 6 個です。(上から i 行目、左から j 列目のマスを (i,j) として、各経路で通るマスを順に示しています)
- (1,1)
- (1,1) → (1,2) → (2,2)
- (1,1) → (2,1) → (2,2)
- (1,2)
- (2,1)
- (2,2)
Score : 600 points
Problem Statement
We have a grid of squares with N rows arranged vertically and N columns arranged horizontally. The square at the i-th row from the top and j-th column from the left has an integer label a_{i,j}.
Consider paths obtained by starting on one of the squares and going right or down to an adjacent square zero or more times. Find the number, modulo 998244353, of such paths that start and end on squares with the same label.
Two paths are distinguished when they visit different sets of squares (including the starting and ending squares).
Constraints
- 1 \leq N \leq 400
- 1 \leq a_{i,j} \leq N^2
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N
a_{1,1} \ldots a_{1,N}
\vdots
a_{N,1} \ldots a_{N,N}
Output
Print the answer.
Sample Input 1
2 1 3 3 1
Sample Output 1
6
The following six paths satisfy the requirements. ((i, j) denotes the square at the i-th row from the top and j-th column from the left. Each path is represented as a sequence of squares it visits.)
- (1,1)
- (1,1) → (1,2) → (2,2)
- (1,1) → (2,1) → (2,2)
- (1,2)
- (2,1)
- (2,2)