Contest Duration: - (local time) (100 minutes) Back to Home
Ex - Yet Another Path Counting /

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

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


• (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}


### 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)