You are given a board. You are asked to draw M horizontal lines and N vertical lines in that board, so that the whole board is divided into (M+1) x (N+1) cells. So there will be M + 1 rows each of which will exactly contain N + 1 cells.

Now you are asked to color every cell. For these purpose, you are given four colors.

            Red

            Green

            Blue

            Orange

To make the board more beautiful and colorful, you have to be careful, so that no two adjacent cells contain the same color. Two cells are considered adjacent if they share a common side.

You are also given some forbidden cells. You must not draw anything in those cells. But you must color every other cell which are not forbidden using a single color.

You have to answer in how many ways you can color this board.

Figure: Some examples of valid and invalid coloring, where M = 1, N = 1 and no forbidden cell.

Input

Input will start with an integer T(T<=50) which indicates the number of test case. Each case will start with two integers M and N (0<=M, N<=6), number of horizontal lines and number of vertical lines. Next line will contain an integer K ( 0<=K<=(M+1)*(N+1) ), which indicates the number of forbidden cells. Each of the next K lines will contain two integers x and y (1<=x<=M+1, 1<=y<=N+1), representing one forbidden cell, which is yth cell of xth row. Each given forbidden cells are distinct.

Output

For each test case, output a single line in the form “Case #: P”, where # will be replaced by the case number and P will be replaced by the number of valid ways you can draw the given board. The result can be very large you should output the result modulo 1000000007.

Sample Input                             Output for Sample Input

Problem Setter: Md. Arifuzzaman Arif, Special Thanks: Mohammad Mahmudur Rahman作法 : 插頭DP

? 可以填入 1 2 3 4 得 010, 020, 030, 040,

--|0
01|?
可以填入 2 3 4 得 012, 013, 014

--|0
02|?
可以填入 1 3 4 得 021, 023, 024

... 我想聰明的你能理解。

接著把最左邊一定為 0 的狀態忽略。

#include <stdio.h>
#include <string.h>
int g[10][10], n, m;
int n5[100000][10];
void build5num() {
    int i, j;
    for(i = 0; i < 100000; i++) {
        n5[i][0] = i;
        for(j = 0; j < 9; j++) {
            n5[i][j+1] = n5[i][j]/5;
            n5[i][j] %= 5;
        }
    }
}
int sol() {
    int i, j, k, l;
    int s5 = 1;
    for(i = 1; i <= m; i++)
        s5 *= 5;
    int dp[2][s5], roll = 0;
    int buf[10], x, p;
    memset(dp[0], 0, sizeof(dp));
    dp[0][0] = 1;
    for(i = 1; i <= n; i++) {
        for(j = 1; j <= m; j++) {
            memset(dp[1-roll], 0, sizeof(dp[0]));
            for(k = 0; k < s5; k++) {
                if(dp[roll][k] == 0)
                    continue;
                if(g[i][j]) {
                    memcpy(buf, n5[k], sizeof(buf));
                    buf[j-1] = 0;
                    x = 0;
                    for(p = m-1; p >= 0; p--)
                        x = x*5 + buf[p];
                    dp[1-roll][x] = dp[1-roll][x] + dp[roll][k];
                    if(dp[1-roll][x] >= 1000000007)
                        dp[1-roll][x] -= 1000000007;
                } else {
                    memcpy(buf, n5[k], sizeof(buf));
                    for(l = 1; l <= 4; l++) {
                        if(n5[k][j-1] != l && (j == 1 || n5[k][j-2] != l)) {
                            buf[j-1] = l;
                            x = 0;
                            for(p = m-1; p >= 0; p--)
                                x = x*5 + buf[p];
                            dp[1-roll][x] = dp[1-roll][x] + dp[roll][k];
                            if(dp[1-roll][x] >= 1000000007)
                                dp[1-roll][x] -= 1000000007;
                        }
                    }
                }
            }
            roll = 1-roll;
        }
    }
    int ans = 0;
    for(i = 0; i < s5; i++) {
        ans += dp[roll][i];
        if(ans >= 1000000007)
            ans -= 1000000007;
    }
    return ans;
}
int main() {
    build5num();
    int t, x, y, k;
    int cases = 0;
    scanf("%d", &t);
    while(t--) {
        scanf("%d %d", &n, &m);
        scanf("%d", &k);
        memset(g, 0, sizeof(g));
        while(k--) {
            scanf("%d %d", &x, &y);
            g[x][y] = 1;
        }
        n++, m++;
        printf("Case %d: %d\n", ++cases, sol());
    }
    return 0;
}