你突然有了一个大房子，房子里面有一些房间。事实上，你的房子可以看做是一个包含n*m个格子的格状矩形，每个格子是一个房间或者是一个柱子。在一开始的时候，相邻的格子之间都有墙隔着。

第一行两个数分别表示n和m。

 一行一个整数，表示合法的方案数 Mod 10^9

对于前100%的数据，n,m<=9

/*by SilverN*/#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>#include<cmath>#include<vector>#define LL long longusing namespace std;const int mod=1e9;//const int mx[5]={0,1,0,-1,0};const int my[5]={0,0,1,0,-1};const int mxn=400;int n,m;int f[mxn][mxn];LL Gauss(int n){    int i,j,k,F=1;    for(i=1;i<=n;i++){        printf("i:%d\n",i);        int p=i;        if(!f[i][i]){            for(j=i+1;j<=n;j++)                if(f[j][i]>f[p][i]){p=j;break;}            F=-F;            for(j=i;j<=n;j++)                swap(f[p][j],f[i][j]);        }        if(!f[i][i]){printf("i!:%d\n",i);return 0;}        for(j=i+1;j<=n;j++){            while(f[j][i]){//辗转相除消到0                 LL x=f[j][i]/f[i][i];                for(k=i;k<=n;k++){                    f[j][k]=((f[j][k]-x*f[i][k]%mod)+mod)%mod;                }                if(!f[j][i])break;                F=-F;                for(k=i;k<=n;k++)swap(f[j][k],f[i][k]);            }        }    }    LL res=1;    for(i=1;i<=n;i++){res=res*f[i][i]%mod;}    res=(res*F+mod)%mod;    return res;}char mp[mxn][mxn];int id[mxn][mxn],cnt=0;void init(){    for(int i=1;i<=n;i++)        for(int j=1;j<=n;j++)            if(mp[i][j]==‘.‘)id[i][j]=++cnt;    return;}int main(){    int i,j;    scanf("%d%d",&n,&m);    for(i=1;i<=n;i++)scanf("%s",mp[i]+1);    init();    for(i=1;i<=n;i++)        for(j=1;j<=n;j++){            if(mp[i][j]!=‘.‘)continue;            for(int k=1;k<=4;k++){                int nx=i+mx[k],ny=j+my[k];                if(nx>0 && nx<=n && ny>0 && ny<=m){                    if(mp[nx][ny]==‘.‘){                        int u=id[i][j],v=id[nx][ny];//                        printf("u:%d v:%d\n",u,v);                        f[u][u]++;                        f[u][v]--;                    }                }            }        }    printf("St\n");    LL ans=Gauss(cnt-1);    printf("%lld\n",ans);    return 0;}