题目描述

憨憨和杰哥住在一个奇妙的城市里。

这个城市可以看作是一张 $N$ 行 $N$ 列的网格图，每个网格点都有一个正整数标签，其中第 $i$ 行第 $j$ 列的正整数标签为 $A_{i, j}$。

他们俩打算来一场“快乐的旅行”，而“快乐的旅行”可以描述为在网格图中的一条只能向右或向下走的路径。

如果一条路径的起点坐标为 $(x_1, y_1)$，终点坐标为 $(x_2, y_2)$，当且仅当这条路径满足以下条件时，我们才会将其称作“快乐的旅行”：

• $1 \le x_1 \le x_2 \le N$
• $1 \le y_1 \le y_2 \le N$
• $A_{x_1, y_1} = A_{x_2, y_2}$

换句话说，只要他们从网格图中的任意一个位置开始，每次向右或向下走任意步（可以是 $0$ 步），最终到达一个仍是网格图内部的位置，并且起点与终点的标签相同的话，那么这种走法就可以称作是“快乐的旅行”。

问，在所有可能的走法当中，总共有多少种走法可以被称作是“快乐的旅行”？你只需要输出这个答案对 $998244353$ 取模后的结果。

只要两种走法在过程中经过的坐标序列不完全一致，那么这两种走法便可以被称作是不同的。

输入格式

第一行包含一个正整数 $N$，表示网格图的大小。

接下来 $N$ 行，每行 $N$ 个正整数，第 $i$ 行第 $j$ 个正整数为 $A_{i, j}$，表示网格图中每个位置的标签。

输出格式

一个整数，表示走法的方案数。

答案可能很大，输出对 $998244353$ 取模后的结果即可。

3
1 3 2
2 1 3
3 2 1

23

数据范围

• 对于 $20\%$ 的测试数据：$1 \le N \le 50$
• 对于 $100\%$ 的测试数据：$1 \le N \le 500$，$1 \le A_{i, j} \le N^2$