路径求和问题

题目描述

有一个 $n$ 行 $m$ 列的网格。网格里的每个格子都写着一个整数，其中第 $i$ 行第 $j$ 列的格子里写着整数 $a_{i,j}$。

令 $(i,j)$ 表示位于第 $i$ 行第 $j$ 列的格子。你现在需要从 $(1,1)$ 出发并前往 $(n,m)$。当位于格子 $(i,j)$ 时，可以选择走到右方的格子 $(i,j+1)$（若 $j<m$），也可以选择走到下方的格子 $(i+1,j)$（若 $i<n$）。

令 $S$ 表示路径上每个格子里的整数形成的集合，包括 $a_{1,1}$ 和 $a_{n,m}$。路径的价值定义为 $S$ 中元素的数量（集合中不包含重复元素）。对于所有可能的路径，求它们的价值之和。

由于答案可能很大，请将答案对 $998244353$ 取模后输出。

输入格式

有多组测试数据。第一行输入一个整数 $T$（$1\le T\le 10^3$）表示测试数据组数。

对于每组测试数据：

• 第一行输入两个整数 $n$ 和 $m$（$1\le n,m\le 2\times 10^5$，$1\le n\times m\le 2\times 10^5$），表示网格的行数和列数。
• 接下来 $n$ 行，第 $i$ 行输入 $m$ 个整数 $a_{i,1},a_{i,2},\cdots,a_{i,m}$（$1\le a_{i,j}\le n\times m$），其中 $a_{i,j}$ 表示格子 $(i,j)$ 里的整数。

保证所有数据 $n\times m$ 之和不超过 $2\times 10^5$。

输出格式

每组数据输出一行一个整数，表示所有可能的路径的价值之和对 $998244353$ 取模后的结果。

样例 #1

样例输入 #1

3
2 3
5 2 1
1 5 5
1 1
1
2 3
3 3 3
3 3 3

样例输出 #1

7
1
3

样例 #1 解释

对于第一组样例数据，有 $3$ 条可能的路径：

• 第一条路径是 $(1,1)\to(1,2)\to(1,3)\to(2,3)$，$S=\{1,2,5\}$，价值为 $3$；
• 第二条路径是 $(1,1)\to(1,2)\to(2,2)\to(2,3)$，$S=\{2,5\}$，价值为 $2$；
• 第三条路径是 $(1,1)\to(2,1)\to(2,2)\to(2,3)$，$S=\{1,5\}$，价值为 $2$。

所以答案是 $3+2+2=7$。

第二组数据只有一个格子，唯一的路径价值为 $1$。

第三组数据所有格子都是 $3$，每条路径的价值都是 $1$，共 $3$ 条路径，答案为 $3$。

数据范围与子任务

对于所有数据：$1\le n,m\le 2\times 10^5$，$1\le n\times m\le 2\times 10^5$，$1\le a_{i,j}\le n\times m$，$\sum(n\times m)\le 2\times 10^5$。