Japanese Bands
题目描述
Grammy 正在设计一款以她喜欢的日本音乐企划 BanG Dream! 为主题的集换式卡牌游戏。游戏中有 n1 张角色卡、n2 张音乐卡。她要给每张卡填上一个 1 到 m 之间的整数,表示卡牌的魔力。
她选定了 k 对整数 (a1,b1),…,(ak,bk),希望每一对数值组合都能在游戏中使用。对于每一对 (ai,bi),赋值方案必须满足以下条件中的至少一个:
- 某张角色卡的数值为 ai,某张音乐卡的数值为 bi。
- 某张音乐卡的数值为 ai,某张角色卡的数值为 bi。
请计算合法赋值方案数。
设所有角色卡上的数值组成多重集合 C,所有音乐卡上的数值组成多重集合 M。当且仅当 C 不同或 M 不同,两个赋值方案才算不同。同一种卡内部不按卡片的位置或编号区分方案。
多重集合允许元素重复;两个多重集合不同,指存在某个数在两个集合中的出现次数不同。限制中没有要求 ai=bi,也没有要求各对整数互不相同。
输入格式
第一行一个整数 T,表示测试用例数。
每个测试用例第一行四个整数 n1,n2,m,k。接下来 k 行,每行两个整数 ai,bi。
输出格式
每个测试用例输出一行一个整数,表示合法方案数对 109+7 取模的结果。
数据范围
- 1≤T≤500。
- 1≤n1,n2≤109,1≤m≤20,1≤k≤m2。
- 1≤ai,bi≤m。
- 每个输入文件中,满足 m>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) 为:
- ({1,2},{1,1,3})、({1,2},{1,2,3})、({1,2},{1,3,3})。
- ({1,3},{1,1,2})、({1,3},{1,2,2})、({1,3},{1,2,3})。
第二个测试用例的四对合法多重集合为 ({1,1},{1,1})、({1,2},{1,1})、({1,1},{1,2})、({1,2},{1,2})。