#P18210. Bingo

Bingo

Bingo

给定两个整数 n,mn,m,以及长度为 nmnm 的整数序列 a1,a2,…,anma_1,a_2,\ldots,a_{nm}。将序列依次填入一个 nn 行 mm 列的网格:第 ii 行、第 jj 列放入 a(i−1)m+ja_{(i-1)m+j}。

如果填入网格后,下列条件至少有一个成立,就称整数 kk 是该序列的 bingo 整数:

  • 至少存在一行,该行所有整数都不大于 kk。
  • 至少存在一列,该列所有整数都不大于 kk。

一个序列可能有多个 bingo 整数,本题只关心其中最小的一个。

对于给定序列的全部 (nm)!(nm)! 个排列,分别求出最小 bingo 整数,并求它们的和。答案对 998244353998244353 取模。

即使有数值相同的元素,也始终计算 (nm)!(nm)! 个排列:各原下标的元素视为不同。

输入格式

有多组测试数据。第一行一个整数 TT,表示测试数据组数。

对于每组数据:

第一行两个整数 n,mn,m,满足 1≤n,m≤2×1051\le n,m\le2\times10^5,1≤nm≤2×1051\le nm\le2\times10^5。

第二行 nmnm 个整数 a1,a2,…,anma_1,a_2,\ldots,a_{nm},满足 0≤ai<9982443530\le a_i<998244353。

保证所有测试数据的 nmnm 之和不超过 4×1054\times10^5。

输出格式

每组数据输出一行一个整数,表示所求和对 998244353998244353 取模的结果。

样例

输入:

4
2 2
1 3 2 4
3 1
10 10 10
1 3
20 10 30
3 4
1 1 4 5 1 4 1 9 1 9 8 10

输出:

56
60
60
855346687

样例说明

第一组数据中,如果 11 和 22 不在同一行或同一列,最小 bingo 整数为 33;否则为 22。前一种情况有 88 个排列,因此答案为

8×3+(4!−8)×2=56.8\times3+(4!-8)\times2=56.

第二组数据中,每个排列的最小 bingo 整数均为 1010,因此答案为 3!×10=603!\times10=60。