题目描述

Grammy 正在以她最喜欢的日本音乐媒体企划 $\textit{BanG Dream!}$ 设计一款新的集换式卡牌游戏（TCG）。按照她的设定，总共有 $n_1$ 张角色卡和 $n_2$ 张音乐卡。现在她需要为每张卡牌分配一个 $1$ 到 $m$（包含 $1$ 和 $m$）之间的整数，表示这张卡包含的魔力值。

在每局 TCG 游戏中，总会有一些特殊连携技可以造成额外伤害。Grammy 现在考虑了一条与卡牌赋值有关的特殊规则。具体来说，给定 $k$ 对整数 $(a_1, b_1), (a_2, b_2), \cdots, (a_k, b_k)$，其中 $1 \le a_i, b_i \le m$。Grammy 想确保每一组这样的数值组合都可以在游戏中被打出。也就是说，对每一对整数 $(a_i, b_i)$，所有卡牌的赋值必须满足以下两个约束中的至少一个：

• 有一张角色卡上的值为 $a_i$，同时有一张音乐卡上的值为 $b_i$。
• 有一张音乐卡上的值为 $a_i$，同时有一张角色卡上的值为 $b_i$。

请你帮助 Grammy 计算，有多少种合法的卡牌赋值方案。

设 $\mathbb{C}$ 表示角色卡上的所有整数的多重集，$\mathbb{M}$ 表示音乐卡上的所有整数的多重集。如果 $\mathbb{C}$ 或 $\mathbb{M}$ 不同，则我们认为两个赋值不同。

注意：一个整数在多重集中可以出现多次。我们说两个多重集 $\mathbb{X}$、$\mathbb{Y}$ 不同，是指存在某个整数 $k$，使得 $k$ 在 $\mathbb{X}$ 和 $\mathbb{Y}$ 中的出现次数不同。

输入格式

有若干组测试数据。输入的第一行包含一个整数 $T$（$1 \le T \le 500$），表示测试数据组数。对于每组测试数据：

第一行输入四个整数 $n_1$、$n_2$、$m$ 和 $k$（$1 \le n_1, n_2 \le 10^9$，$1 \le m \le 20$，$1 \le k \le m^2$）。

接下来 $k$ 行中，第 $i$ 行输入两个整数 $a_i$ 和 $b_i$（$1 \le a_i, b_i \le m$）。

保证最多只有 $5$ 组测试数据满足 $m > 10$。

输出格式

对于每组测试数据，输出一行一个整数，表示合法卡牌赋值方案的数量。由于答案可能很大，输出对 $(10^9 + 7)$ 取模的结果。

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

提示

对于第一个样例测试，合法的 $(\mathbb{C}, \mathbb{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\})$。

对于第二个样例测试，合法的 $(\mathbb{C}, \mathbb{M})$ 有这几组：$(\{1, 1\}, \{1, 1\})$，$(\{1, 2\}, \{1, 1\})$，$(\{1, 1\}, \{1, 2\})$ 和 $(\{1, 2\}, \{1, 2\})$。

由 ChatGPT 5 翻译