网格覆盖

Grade Open Time Friday, 19 September 2014, 10:08 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:08 am
Allow late Yes Close Time Friday, 26 September 2014, 10:08 am
Input file ignoretheblocks.in Output file ignoretheblocks.out

【题目描述】

今天是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