#P11715. [清华集训 2014] 简单回路

    ID: 13089 远端评测题 1000ms 512MiB 尝试: 0 已通过: 0 难度: 6 上传者: 标签>2014插头 DPCTT(清华集训/北大集训)

[清华集训 2014] 简单回路

题目描述

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

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

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

现在有 QQ 个询问,每次询问有多少条合法的简单回路经过了 (x,y)(x,y)(x+1,y)(x+1,y) 之间的边。

输入格式

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

接下来 kk 行,每行两个正整数 x,yx,y (1xn,1ym)(1 \leq x \leq n,1 \leq y \leq m),表示 (x,y)(x,y) 为一个障碍点(可能重复)

接下来一个整数 QQ,表示 QQ 个询问。

接下来 QQ 行,每行两个正整数 x,yx,y (1xn1,1ym)(1 \leq x \leq n-1, 1 \leq y \leq m),询问有多少条合法的简单回路经过了格子 (x,y)(x,y)(x+1,y)(x+1,y) 之间的边。

输出格式

输出 QQ 行,每行对应一组询问。请将答案 mod(1000000000+7)\bmod (1000000000+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
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
18156
27456
235
1496
26496
8034
96
2373
4982
26496

提示

测试点编号 nn mm kk qq
11 100100 11 100≤ 100 100≤ 100
22 10001000 22
33
44 33
55 55
66 66
77 10000≤ 10000
88
99
1010