UOJ Logo Universal Online Judge

UOJ

#39. 【清华集训2014】简单回路

统计

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

  1. 不经过任何一个障碍点
  2. 回路不自交

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

现在有 $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$

时间限制:$1\texttt{s}$

空间限制:$512\texttt{MB}$

来源

中国国家队清华集训2014~2015 Day 2 - By 彭天翼

下载

样例数据下载