#include <bits/stdc++.h> using namespace std; int t, n, m, g[12][12], dp[12][12][1<<12], mod = 1e9+7; int main(){ cin >> t; for (int Case = 1; Case <= t; Case++){ cin >> n >> m; for (int i = 1; i <= n; i++){ for (int j = 1; j <= m; j++){ cin >> g[i][j]; } } memset(dp, 0, sizeof(dp)); dp[0][m][0] = 1; // 使用動態規劃計算狀態 for (int i = 1; i <= n; i++){ for (int j = 0; j < (1<<m); j++){ dp[i][0][j<<1] = dp[i-1][m][j]; } for (int j = 1; j <= m; j++){ int x = (1<<(j-1)); // 第 j 個位元為 1，代表蛇的身體的一部分 int y = (1<<j); // 第 j+1 個位元為 1，代表蛇的身體的另一部分 if (g[i][j] == 0){ // 如果是插座位置，不放置蛇 for (int s = 0; s < (1<<(m+1)); s++){ if ((s&x) || (s&y)){ // 如果 s 的第 j 或第 j+1 個位元為 1，表示插座位置已被蛇佔據 dp[i][j][s] = 0; } else dp[i][j][s] = dp[i][j-1][s]; // 否則，狀態與上一列同一行的相同 } } else{ // 如果是非插座位置，放置蛇 for (int s = 0; s < (1<<(m+1)); s++){ dp[i][j][s] = dp[i][j-1][s^x^y]; // 佔據插座位置的狀態 if (!!(s&x) != !!(s&y)) dp[i][j][s] += dp[i][j-1][s]; // 若 s 的第 j 和第 j+1 個位元只有一個為 1，則可以放置蛇 dp[i][j][s] %= mod; } } } } cout << "Case " << Case << ": " << dp[n][m][0] << "\n"; } }