#P18268. Japanese Bands

Japanese Bands

Japanese Bands

题目描述

Grammy 正在设计一款以她喜欢的日本音乐企划 BanG Dream! 为主题的集换式卡牌游戏。游戏中有 n1n_1 张角色卡、n2n_2 张音乐卡。她要给每张卡填上一个 11 到 mm 之间的整数,表示卡牌的魔力。

她选定了 kk 对整数 (a1,b1),…,(ak,bk)(a_1,b_1),\ldots,(a_k,b_k),希望每一对数值组合都能在游戏中使用。对于每一对 (ai,bi)(a_i,b_i),赋值方案必须满足以下条件中的至少一个:

  • 某张角色卡的数值为 aia_i,某张音乐卡的数值为 bib_i。
  • 某张音乐卡的数值为 aia_i,某张角色卡的数值为 bib_i。

请计算合法赋值方案数。

设所有角色卡上的数值组成多重集合 CC,所有音乐卡上的数值组成多重集合 MM。当且仅当 CC 不同或 MM 不同,两个赋值方案才算不同。同一种卡内部不按卡片的位置或编号区分方案。

多重集合允许元素重复;两个多重集合不同,指存在某个数在两个集合中的出现次数不同。限制中没有要求 ai≠bia_i\ne b_i,也没有要求各对整数互不相同。

输入格式

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

每个测试用例第一行四个整数 n1,n2,m,kn_1,n_2,m,k。接下来 kk 行,每行两个整数 ai,bia_i,b_i。

输出格式

每个测试用例输出一行一个整数,表示合法方案数对 109+710^9+7 取模的结果。

数据范围

  • 1≤T≤5001\le T\le500。
  • 1≤n1,n2≤1091\le n_1,n_2\le10^9,1≤m≤201\le m\le20,1≤k≤m21\le k\le m^2。
  • 1≤ai,bi≤m1\le a_i,b_i\le m。
  • 每个输入文件中,满足 m>10m>10 的测试用例至多有五个。

样例

3
2 3 3 3
2 3
1 1
2 3
2 2 2 1
1 1
1 1 10 2
1 2
1 3
6
4
0

样例说明

第一个测试用例的六对合法多重集合 (C,M)(C,M) 为:

  • ({1,2},{1,1,3})(\{1,2\},\{1,1,3\})、({1,2},{1,2,3})(\{1,2\},\{1,2,3\})、({1,2},{1,3,3})(\{1,2\},\{1,3,3\})。
  • ({1,3},{1,1,2})(\{1,3\},\{1,1,2\})、({1,3},{1,2,2})(\{1,3\},\{1,2,2\})、({1,3},{1,2,3})(\{1,3\},\{1,2,3\})。

第二个测试用例的四对合法多重集合为 ({1,1},{1,1})(\{1,1\},\{1,1\})、({1,2},{1,1})(\{1,2\},\{1,1\})、({1,1},{1,2})(\{1,1\},\{1,2\})、({1,2},{1,2})(\{1,2\},\{1,2\})。