Colorful Board

內容 ： 正體->简体
給你一個板子，在上面M條水平線跟N條垂直線，因此在整個板子有(M+1) x (N+1)格子，現在請你在每個格子上填上顏色，總共有4種顏色Red,Green,Blue,Orange。

為了使板子更加漂亮，你必須小心一件事情，兩鄰的格子不能有相同的顏色(相鄰的定義是有共同的邊)，但是有些格子是被禁止塗上任何顏色的，題目來了，你必須回答有幾種方式可以塗完，但不觸犯以上規則。

輸入說明 ：
第一個數字T(T<=50)代表有幾組冊資，每一組測資會給兩格數字M,N ( 0 < M , N < = 6 )代表有幾條水平線跟垂直線，下一行但表有幾格被禁止不能圖畫的個數K( 0 < = K < = ( M + 1 ) * ( N + 1 ) ),接下來K行會包含兩個數字X，Y (1<=x<=M+1, 1<=y<=N+1)，代表第X行的第Y個是被禁止塗畫。

輸出說明 ：
對於每一個測資，請輸出一行 "Case #K: P"，K代表第幾組測試資料，P代表有幾種可能，由於答案可能很大，請mod 1000000007

範例輸入 ：

2
1 1
1
2 1
0 0
0
範例輸出 ：

Case 1: 36
Case 2: 4