OI题库

【题目描述】

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

【输入格式】

输入包含至多100组数据。

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

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

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

【输出格式】

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

【样例输入】

2 2 0

2 4 0

2 4 2

0 0

0 3

0 0 0

【样例输出】

Case 1: 2

Case 2: 5

Case 3: 1

【提示】

对于30%的数据，1<=C<=10.

对于50%的数据,1<=C<=1000.

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

【来源】

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

UVa11741 Ignore the Blocks