当前没有测试数据。

Ex - 又一个路径计数

得分：600分

问题描述

我们有一个由$N$行垂直排列和$N$列水平排列的方形网格。位于从上起第$i$行、从左起第$j$列的方格上有一个整数标签$a_{i,j}$。
考虑通过从一个方格出发，向右或向下前进到相邻方格零次或多次形成的路径。求满足起点和终点方格上标签相同的路径数量，取模$998244353$。
不同的路径在访问的方格集合（包括起点和终点方格）不同时被区分。

约束条件

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

以下六个路径满足要求。($(i, j)$表示从上起第$i$行、从左起第$j$列的方格。每条路径表示为经过的方格序列。)

• $(1, 1)$
• $(1, 1)$ → $(1, 2)$ → $(2, 2)$
• $(1, 1)$ → $(2, 1)$ → $(2, 2)$
• $(1, 2)$
• $(2, 1)$
• $(2, 2)$