#P18588. Referee Without Red

Referee Without Red

Referee Without Red

一个舞团排成 nn 行 mm 列的矩阵。第 ii 行第 jj 列的舞者种类为 ai,ja_{i,j};同一种类可以出现多次。

指挥可以任意次执行以下两类操作,包括一次也不执行:

  • 选择一行,将这一行从左到右编号为 1,2,…,m1,2,\ldots,m,把偶数位置的舞者移到行末。原奇数位置的舞者保持相对顺序,原偶数位置的舞者也保持相对顺序。
  • 选择一列,将这一列从上到下编号为 1,2,…,n1,2,\ldots,n,把偶数位置的舞者移到列末。同样保持两部分内部的相对顺序。

因此,一行操作后按原位置排列为 1,3,5,…,2,4,6,…1,3,5,\ldots,2,4,6,\ldots;列操作的含义相同。每次操作都按照当时的位置重新编号。

原题示意:操作第2行

当且仅当至少有一个位置上的舞者种类不同,两个矩阵才视为不同;交换同种舞者不产生新的矩阵。

求能够得到的不同矩阵数量,对 998244353998244353 取模。

输入格式

第一行一个整数 TT,表示测试用例数量。

对于每个测试用例:

  • 第一行两个整数 n,mn,m。
  • 接下来 nn 行,每行 mm 个整数,第 ii 行为 ai,1,…,ai,ma_{i,1},\ldots,a_{i,m}。

输出格式

每个测试用例输出一行一个整数,表示不同可达矩阵数量对 998244353998244353 取模的结果。

数据范围

1≤T≤1051\le T\le10^5,2≤n,m≤1062\le n,m\le10^6,1≤ai,j≤3×1061\le a_{i,j}\le3\times10^6。

所有测试用例的 n×mn\times m 之和不超过 3×1063\times10^6。

样例输入

2
4 4
1 2 3 4
3 4 1 2
1 2 4 1
4 3 3 2
3 9
1 8 1 1 8 1 1 8 1
1 8 8 8 8 8 8 8 1
1 1 1 8 8 8 1 1 1

样例输出

96
6336