AOJ2393.cpp

#include <bits/stdc++.h>

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(),(x).end()

using namespace std;

typedef long long ll;
typedef long double ld;

const ld eps = 1e-9, pi = acos(-1.0);

const int mod = 1000000007;

struct Mod {
  int num;
  Mod () : num(0) {;}
  Mod (int n) : num((n % mod + mod) % mod) {;}
  operator int() { return num; }
};

Mod operator+(Mod a, Mod b) { return Mod((a.num + b.num) % mod); }
Mod operator-(Mod a, Mod b) { return Mod((mod + a.num - b.num) % mod); }
Mod operator*(Mod a, Mod b) { return Mod(((long long)a.num * b.num) % mod); }
Mod operator+=(Mod &a, Mod b) { return a = a + b; }
Mod operator-=(Mod &a, Mod b) { return a = a - b; }
Mod operator*=(Mod &a, Mod b) { return a = a * b; }
Mod operator^(Mod a, int n) {
  if (n == 0) return Mod(1);
  Mod res = (a * a) ^ (n / 2);
  if (n % 2) res = res * a;
  return res;
}
Mod inv(Mod a) { return a ^ (mod - 2); }
Mod operator/(Mod a, Mod b) { return a * inv(b); }

typedef Mod Data;

struct myhash {
  vector<Data> v;
  myhash() : v(160) {;}
  Data operator[] (int key) const { return v[key%160]; }
  Data &operator[] (int key) { return v[key%160]; }
};

typedef myhash Array;
typedef vector<Array> Matrix;

bool is_zero(Mod a) { return a.num == 0; }

Data det(Matrix &A) {
  const int n = A.size();
  Data D = Data(1);
  for (int i = 0; i < n; ++i) {
    int pivot = i;
    for (int j = i+1; j < min(n, i+32); ++j)
      if (abs(A[j][i]) > abs(A[pivot][i])) pivot = j;
    swap(A[pivot], A[i]);
    D = D * A[i][i] * Data(i != pivot ? -1 : 1);
    if (is_zero(A[i][i])) break;
    Mod invi = inv(A[i][i]);
    for(int j = i+1; j < min(n, i+32); ++j)
      for(int k = min(i+32, n-1); k >= i; --k)
        A[j][k] = A[j][k] - A[i][k] * A[j][i] * invi;
  }
  return D;
}

int H, W, n;
int id[512][16];
string b[512];

void add_edge(Matrix &mat, int a, int b) {
  if (a < n-1 && b < n-1) mat[a][b] -= 1, mat[b][a] -= 1;
  if (a < n-1) mat[a][a] += 1;
  if (b < n-1) mat[b][b] += 1;
}

int main() {
  for (int c = 1; cin >> H >> W, H; ++c) {
    n = 0;
    REP(i,H) cin >> b[i];
    REP(i,H) REP(j,W)
      if (b[i][j] == '.') id[i][j] = n++;
    Matrix mat(n-1);
    REP(i,H) REP(j,W-1)
      if (b[i][j] == '.' && b[i][j+1] == '.')
        add_edge(mat, id[i][j], id[i][j+1]);
    REP(i,H-1) REP(j,W)
      if (b[i][j] == '.' && b[i+1][j] == '.')
        add_edge(mat, id[i][j], id[i+1][j]);
    cout << "Case " << c << ": " << det(mat) << endl;
  }
  return 0;
}