Grammy 正在设计一款基于她最喜爱的日本音乐媒体系列《BanG Dream!》的集换式卡牌游戏（TCG）。根据她的设计，总共有 $n_1$ 张角色卡和 $n_2$ 张音乐卡。现在，她需要为每张卡片分配一个 $1$ 到 $m$ 之间的整数（包含 $1$ 和 $m$），代表该卡片所蕴含的魔法力量。

在每一场 TCG 游戏中，必须存在某些特定的组合才能造成额外伤害。Grammy 现在正在考虑一条与卡片分配数值相关的特殊规则。具体来说，给定 $k$ 对整数 $(a_1, b_1), (a_2, b_2), \dots, (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}$ 不同，则称这两个分配方案是不同的。 回想一下，一个整数可以在多重集中出现多次。如果存在一个整数 $k$，使得 $k$ 在 $\mathbb{X}$ 中出现的次数与在 $\mathbb{Y}$ 中出现的次数不同，则称两个多重集 $\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$)。 保证满足 $m > 10$ 的测试数据不超过 $5$ 组。

输出格式

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

样例

输入 1

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

输出 1

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\})$。