#P18210. Bingo
Bingo
Bingo
给定两个整数 ,以及长度为 的整数序列 。将序列依次填入一个 行 列的网格:第 行、第 列放入 。
如果填入网格后,下列条件至少有一个成立,就称整数 是该序列的 bingo 整数:
- 至少存在一行,该行所有整数都不大于 。
- 至少存在一列,该列所有整数都不大于 。
一个序列可能有多个 bingo 整数,本题只关心其中最小的一个。
对于给定序列的全部 个排列,分别求出最小 bingo 整数,并求它们的和。答案对 取模。
即使有数值相同的元素,也始终计算 个排列:各原下标的元素视为不同。
输入格式
有多组测试数据。第一行一个整数 ,表示测试数据组数。
对于每组数据:
第一行两个整数 ,满足 ,。
第二行 个整数 ,满足 。
保证所有测试数据的 之和不超过 。
输出格式
每组数据输出一行一个整数,表示所求和对 取模的结果。
样例
输入:
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
样例说明
第一组数据中,如果 和 不在同一行或同一列,最小 bingo 整数为 ;否则为 。前一种情况有 个排列,因此答案为
第二组数据中,每个排列的最小 bingo 整数均为 ,因此答案为 。