P11715 [清华集训 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)$ 之后输出。

| 测试点编号 | $n$ | $m$ | $k$ | $q$ | |:------------:|:---------:|:---------:|:---------:|:---------:| | $1$ | $100$ | $1$ | $≤ 100$ | $≤ 100$ | | $2$ | $1000$ | $2$ | $≤ 100$ | $≤ 100$ | | $3$ | $1000$ | $2$ | $≤ 100$ | $≤ 100$ | | $4$ | $1000$ | $3$ | $≤ 100$ | $≤ 100$ | | $5$ | $1000$ | $5$ | $≤ 100$ | $≤ 100$ | | $6$ | $1000$ | $6$ | $≤ 100$ | $≤ 100$ | | $7$ | $1000$ | $6$ | $≤ 100$ | $≤ 10000$ | | $8$ | $1000$ | $6$ | $≤ 100$ | $≤ 10000$ | | $9$ | $1000$ | $6$ | $≤ 100$ | $≤ 10000$ | | $10$ | $1000$ | $6$ | $≤ 100$ | $≤ 10000$ |