在一个有障碍点的 n 行 m 列的网格图中,我们用 (x,y) 来表示第 x 行第 y 列的格子。如果该网格图中的回路满足下面两个条件:
- 不经过任何一个障碍点
- 回路不自交
则我们称该回路为合法的简单回路。
现在有 Q 个询问,每次询问有多少条合法的简单回路经过了 (x,y) 与 (x+1,y) 之间的边。
输入格式
第一行输入三个非负整数 n, m, k,表示 n 行 m 列的网格图中有 k 个障碍点。
接下来 k 行,每行两个正整数x,y (1≤x≤n,1≤y≤m),表示 (x,y) 为一个障碍点(可能重复)
接下来一个整数 Q,表示 Q 个询问。
接下来 Q 行,每行两个正整数 x,y (1≤x≤n−1,1≤y≤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 |