在一个有障碍点的 $n$ 行 $m$ 列的网格图中，我们用 $(x,y)$ 来表示第 $x$ 行第 $y$ 列的格子。如果该网格图中的回路满足下面两个条件：
- 不经过任何一个障碍点
- 回路不自交
则我们称该回路为合法的简单回路。
现在有 $Q$ 个询问，每次询问有多少条合法的简单回路经过了 $(x,y)$ 与 $(x+1,y)$ 之间的边。
输入格式
第一行输入三个非负整数 $n$, $m$, $k$，表示 $n$ 行 $m$ 列的网格图中有 $k$ 个障碍点。
接下来 $k$ 行，每行两个正整数$x, y$ $(1 \leq x \leq n,1 \leq y \leq m)$，表示 $(x,y)$ 为一个障碍点（可能重复）
接下来一个整数 $Q$，表示 $Q$ 个询问。
接下来 $Q$ 行，每行两个正整数 $x,y$ $(1 \leq x \leq n-1, 1 \leq y \leq m)$，询问有多少条合法的简单回路经过了格子 $(x,y)$ 与 $(x+1,y)$ 之间的边。
输出格式
输出 $Q$ 行，每行对应一组询问。请将答案 $\bmod (1000000000+7)$ 之后输出。
样例一
input
4 4 4 2 2 2 4 3 2 4 4 4 1 1 1 4 3 3 2 2
output
1 0 1 0
样例二
input
1000 2 10 426 2 595 2 665 1 447 2 604 2 202 1 26 1 79 1 291 2 6 2 10 932 1 857 2 31 1 458 1 793 1 691 1 438 1 404 1 541 1 872 2
output
18156 27456 235 1496 26496 8034 96 2373 4982 26496
限制与约定
| 测试点编号 | $n$ | $m$ | $k$ | $q$ |
|---|---|---|---|---|
| 1 | $100$ | $1$ | $\leq 100$ | $\leq 100$ |
| 2 | $1000$ | $2$ | $\leq 100$ | $\leq 100$ |
| 3 | $1000$ | $2$ | $\leq 100$ | $\leq 100$ |
| 4 | $1000$ | $3$ | $\leq 100$ | $\leq 100$ |
| 5 | $1000$ | $5$ | $\leq 100$ | $\leq 100$ |
| 6 | $1000$ | $6$ | $\leq 100$ | $\leq 100$ |
| 7 | $1000$ | $6$ | $\leq 100$ | $\leq 10000$ |
| 8 | $1000$ | $6$ | $\leq 100$ | $\leq 10000$ |
| 9 | $1000$ | $6$ | $\leq 100$ | $\leq 10000$ |
| 10 | $1000$ | $6$ | $\leq 100$ | $\leq 10000$ |