1527. [UVa 11741] 网格覆盖

【题目描述】

今天是 $Tilliby$ 的九岁生日。他收到了各种各样的礼物，例如夜光贴纸，电子计算器，一个新牙刷等等。但是，这个看上去很有趣的多米诺瓷砖拼图吸引了他的注意力。拼图的规则如下所述：拼图由一个 $R*C$ 的网格组成，并且它必须完全被 $2*1$ 的瓷砖填充，瓷砖的数量充足。瓷砖不可以重叠。为了使事情复杂化，网格中一些特定的格子被标记为不可使用，它们不能被瓷砖覆盖。不过，除此之外的所有格子都必须恰好被一块瓷砖覆盖。现在，尽管有不可用的格子，这对 $Tilliby$ 来说就是一个简单的练习。但是，如果要计算出覆盖的方案总数，即使他闪亮的新计算器也帮不了他了。你能帮助他吗？

【输入格式】

输入包含至多 $100$ 组数据。

每组数据的第一行有 $3$ 个正整数 $R,C,N$。

接下来有 $N$ 行，每行有两个整数 $r_i,c_i$。其中 $r_i$ 是第 $i$ 个不可用格子的行数，$c_i$ 是它的列数。其中，$1 \leq R \leq 4，1 \leq C \leq 100000000，0 \leq N \leq 100，0 \leq r_i<R，0 \leq c_i<C$。

输入结束标志为 $R=C=N=0$，这组数据不用处理。

【输出格式】

每组数据输出一行，格式为"$Case$ $c:$ $x$"，其中 $c$ 是数据编号（从 $1$ 开始），$x$ 是填充方案总数。由于 $x$ 有可能很大，因此只需输出 $x$ 模 $10000007$ 的值。

【样例1输入】

2 2 0
2 4 0
2 4 2
0 0
0 3
0 0 0

【样例1输出】

Case 1: 2
Case 2: 5
Case 3: 1

【样例2】

点击下载样例2 

【提示】

对于 $30\%$ 的数据，$1 \leq C \leq 10$.

对于 $50\%$ 的数据,$1 \leq C \leq 1000$.

对于 $100\%$ 的数据，范围如题中所示。

【来源】

Problem setter: Samee Zahur Special Thanks: Md. Arifuzzaman Arif

UVa11741 Ignore the Blocks