题目描述

在一个有障碍点的 $n$ 行 $m$ 列的网格图中，我们用 $(x,y)$ 来表示第 $x$ 行第 $y$ 列的格子。如果该网格图中的回路满足下面两个条件：

• 不经过任何一个障碍点；

• 回路不自交。

则我们称该回路为合法的简单回路。

现在有 $q$ 个询问，每次询问有多少条合法的简单回路经过了 $(a,b)$ 与 $(a+1,b)$ 之间的边。

输入格式

第一行输入三个非负整数 $n,m,k$，表示 $n$ 行 $m$ 列的网格图中有 $k$ 个障碍点。

接下来 $k$ 行，每行两个正整数 $x,y$，表示 $(x,y)$ 为一个障碍点（可能重复）。

接下来一个整数 $q$，表示 $q$ 个询问。

接下来 $q$ 行，每行两个正整数 $a,b$，询问有多少条合法的简单回路经过了格子 $(a,b)$ 与 $(a+1,b)$ 之间的边。

输出格式

共 $q$ 行，每行对应一组询问答案对 $10^9+7$ 取模后的值。

4 4 4
2 2
2 4
3 2
4 4
4
1 1
1 4
3 3
2 2

1
0
1
0

数据规模与约定

对于 $100\%$ 的数据，$1\leq n\leq 10^3$，$1\leq m\leq 6$，$1\leq k\leq 100$，$1\leq q\leq 10^4$，$1\leq x\leq n$，$1\leq y\leq m$，$1\leq a<n$，$1\leq b\leq m$。

来源

$2015$ 年国家集训队测试。