又一个路径计数

题目描述

有一个纵向 $N$ 行、横向 $N$ 列的网格。从顶部数第 $i$ 行、从左数第 $j$ 列的格子写有整数标签 $a_{i,j}$。

考虑从某个格子出发,向右或向下移动到相邻格子,移动 $0$ 次或多次得到的路径。求起点和终点格子上标签相同的路径的个数,结果对 $998244353$ 取模。

两条路径访问的格子集合不同(包括起点和终点)时,视为不同的路径。

输入格式

输入按以下格式从标准输入给出:

N
a_{1,1} … a_{1,N}
⋮
a_{N,1} … a_{N,N}

输出格式

输出答案。

样例

2
1 3
3 1

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

数据范围

• $1 \le N \le 400$
• $1 \le a_{i,j} \le N^2$
• 输入中的所有值均为整数。