配点 : $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}$

出力

答えを出力せよ。

2
1 3
3 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)$