正如题目名称所示，本题与迷宫有关，具体为一个 $N$ 行 $M$ 列的二维迷宫（$N \le M$），其中行从上到下编号为 $1$ 到 $N$，列从左到右编号为 $1$ 到 $M$。第 $i$ 行第 $j$ 列的单元格记为 $(i, j)$。

迷宫只有一个入口 $(1, 1)$ 和一个出口 $(N, M)$。为简化起见，你每一步只能向右或向下移动。迷宫中可能存在不可经过的障碍物单元格，也可能存在必须经过的宝藏单元格。

在本题中，你需要计算从起点到终点的合法路径数量。

迷宫中有 $S$ 个宝藏单元格。合法路径必须经过所有宝藏单元格。

对于以下障碍物单元格，合法路径不能经过任何障碍物： 所有满足 $x > y$ 的单元格 $(x, y)$， 所有满足 $M + x < N + y$ 的单元格 $(x, y)$， * 以及额外给定的 $K$ 个障碍物单元格。

输入格式

第一行输入一个整数 $T$ ($1 \le T \le 10$)，表示测试用例的数量。接下来是 $T$ 组测试用例。

每个测试用例的第一行包含四个整数 $N, M, S$ 和 $K$。($1 \le N \le M \le 100000, 0 \le S \le 10, 0 \le K \le 20$)

接下来 $S$ 行，每行包含两个整数 $x$ 和 $y$，表示迷宫中的宝藏单元格。($1 \le x \le N, 1 \le y \le M, x \le y, M + x \ge N + y$)（没有两个宝藏单元格位于同一位置）

之后是 $K$ 行，每行包含两个整数 $x$ 和 $y$，表示迷宫中的障碍物单元格。($1 \le x \le N, 1 \le y \le M, x \le y, M + x \ge N + y$)（没有两个障碍物单元格位于同一位置）

输出格式

对于每个测试用例，输出一行 “Case #x: y”，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是合法路径的数量，结果对 $1,000,000,007$ ($10^9 + 7$) 取模。

样例

输入 1

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

输出 1

Case #1: 1
Case #2: 2

说明

在样例 1 中，一条合法路径为：

在样例 2 中，两条合法路径为：