题目描述

我们有一个 $N$ 行 $N$ 列的方格网格。左上角到右下角一共有 $2N-1$ 条路径，每条路径由一系列向右或向下的移动组成。方格 $(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}$

输出

输出答案。

示例输入 1

2
1 3
3 1

示例输出 1

6

以下六条路径满足要求。$(i, j)$ 表示左上角到右下角路径上的方格，每条路径表示为访问的方块序列。

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