The king demon is waiting in his dungeon to defeat a brave man. His dungeon consists of H \times W grids. Each cell is connected to four (i.e. north, south, east and west) neighboring cells and some cells are occupied by obstacles.

To attack the brave man, the king demon created and sent a servant that walks around in the dungeon. However, soon the king demon found that the servant does not work as he wants. The servant is too dumb. If the dungeon had cyclic path, it might keep walking along the cycle forever.

In order to make sure that the servant eventually find the brave man, the king demon decided to eliminate all cycles by building walls between cells. At the same time, he must be careful so that there is at least one path between any two cells not occupied by obstacles.

Your task is to write a program that computes in how many ways the kind demon can build walls.



Input

The first line of each test case has two integers H and W (1 \leq H \leq 500, 1 \leq W \leq 15), which are the height and the width of the dungeon. Following H lines consist of exactly W letters each of which is '.' (there is no obstacle on the cell) or '#' (there is an obstacle). You may assume that there is at least one cell that does not have an obstacle.

The input terminates when H = 0 and W = 0. Your program must not output for this case.

Output

For each test case, print its case number and the number of ways that walls can be built in one line. Since the answer can be very big, output in modulo 1,000,000,007.

Example

Input

2 2
..
..
3 3
...
...
..#
0 0


Output

Case 1: 4
Case 2: 56
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;



typedef vector<ll> V;
typedef vector<V> MATRIX;


int H,W;
int height,width;
int num_case;
int diff_row[4] = {-1,0,0,1},diff_col[4] = {0,-1,1,0};
ll table[505][20];
char base_map[505][20];


bool rangeCheck(int row,int col){

	return row >= 0 && row <= H-1 && col >= 0 && col <= W-1;
}

ll gcd(ll x,ll y){

	x = abs(x);
	y = abs(y);

	if(x < y){
		swap(x,y);
	}
	if(y == 0){
		return x;
	}else{
		return gcd(y,x%y);
	}
}

ll lcm(ll x,ll y){

	return (x*y)/gcd(x,y);
}

ll extgcd(ll a,ll b,ll &x,ll &y){
	ll d = a;
	if(b != 0){
		d = extgcd(b,a%b,y,x);
		y -= (a/b)*x;
	}else{
		x = 1;
		y = 0;
	}
	return d;
}

ll mod_inverse(ll a,ll m){
    ll x,y;
    extgcd(a,m,x,y);
    return (m+x%m)%m;
}

ll determinant(MATRIX A){

	MATRIX C(height,V(width));

	for(int row = 0; row < height; row++){
		for(int col = 0; col < width; col++){
			C[row][col] = A[row][col];
		}
	}

	int RANGE = W;

	ll mult = 1;

	for(int base = 0; base < height-1; base++){

		int row = -1;

		if(C[base][W] != 0){

			row = base;
		}else{

			for(int k = 1; k <= RANGE && base+k < height; k++){

				if(C[base+k][W-k] != 0){

					row = base+k;

					for(int a = 0; a < 2*W+1; a++){

						swap(C[base+k][W-k+a],C[base][W+a]);
					}

					mult *= (-1+MOD);
					mult %= MOD;
					break;
				}
			}

			if(row == -1)return 0;
		}

		for(int k = 1; k <= RANGE && base+k < height; k++){

			if(C[base+k][W-k] == 0)continue;

			ll LCM = lcm(C[base][W],C[base+k][W-k]);

			ll mult_base = LCM/C[base][W];
			ll mult_k = LCM/C[base+k][W-k];

			mult *= mult_k;
			mult %= MOD;

			for(int a = 0; a < 2*W+1; a++){

				C[base+k][W-k+a] *= mult_k;
				C[base+k][W-k+a] %= MOD;
			}

			for(int a = 0; a < 2*W+1; a++){

				C[base+k][W-k+a] -= C[base][W+a]*mult_base;

				if(C[base+k][W-k+a] < 0){
					C[base+k][W-k+a] = abs(C[base+k][W-k+a])%MOD;
					C[base+k][W-k+a] *= -1;
					C[base+k][W-k+a] += MOD;
				}
			}
		}
	}

	ll ret = 1;
	for(int i = 0; i < height; i++){

		ret *= C[i][W];
		ret %= MOD;
	}

	ret *= mod_inverse(mult,MOD);

	return ret%MOD;
}


void func(){

	for(int row = 0; row < H; row++){

		scanf("%s",base_map[row]);
	}

	int index = 0;

	for(int row = 0; row < H; row++){
		for(int col = 0; col < W; col++){

			if(base_map[row][col] == '#')continue;

			table[row][col] = index++;
		}
	}

	height = index-1;
	width = 3*W+1;

	MATRIX A(height,V(width));

	for(int row = 0; row < height; row++){
		for(int col = 0; col < width; col++){

			A[row][col] = 0;
		}
	}

	for(int row = 0; row < H; row++){
		for(int col = 0; col < W; col++){

			if(base_map[row][col] == '#' || table[row][col] == index-1)continue;

			for(int i = 0; i < 4; i++){

				int adj_row = row+diff_row[i];
				int adj_col = col+diff_col[i];

				if(rangeCheck(adj_row,adj_col) == false || base_map[adj_row][adj_col] == '#')continue;

				if(table[adj_row][adj_col] != index-1){

					A[table[row][col]][table[adj_row][adj_col]-table[row][col]+W] = -1+MOD;
				}

				A[table[row][col]][W]++;
			}
		}
	}

	printf("Case %d: %lld\n",num_case++,abs(determinant(A)));
}


int main(){

	num_case = 1;

	while(true){

		scanf("%d %d",&H,&W);
		if(H == 0 && W == 0)break;

		func();
	}

	return 0;
}

