#P18588. Referee Without Red
Referee Without Red
Referee Without Red
一个舞团排成 行 列的矩阵。第 行第 列的舞者种类为 ;同一种类可以出现多次。
指挥可以任意次执行以下两类操作,包括一次也不执行:
- 选择一行,将这一行从左到右编号为 ,把偶数位置的舞者移到行末。原奇数位置的舞者保持相对顺序,原偶数位置的舞者也保持相对顺序。
- 选择一列,将这一列从上到下编号为 ,把偶数位置的舞者移到列末。同样保持两部分内部的相对顺序。
因此,一行操作后按原位置排列为 ;列操作的含义相同。每次操作都按照当时的位置重新编号。

当且仅当至少有一个位置上的舞者种类不同,两个矩阵才视为不同;交换同种舞者不产生新的矩阵。
求能够得到的不同矩阵数量,对 取模。
输入格式
第一行一个整数 ,表示测试用例数量。
对于每个测试用例:
- 第一行两个整数 。
- 接下来 行,每行 个整数,第 行为 。
输出格式
每个测试用例输出一行一个整数,表示不同可达矩阵数量对 取模的结果。
数据范围
,,。
所有测试用例的 之和不超过 。
样例输入
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