Description

You suddenly have a big house with some rooms in it. In fact, your house can be seen as a lattice rectangle with n*m cells, each of which is a room or a column. At the beginning, there were walls between adjacent cells.

You want to break through the walls of some adjacent rooms so that all the rooms can reach each other. In the process, you can't punch through the house or get through the columns (and the walls next to them). At the same time, you don't want to be hard to catch when there are thieves in the house, so you want to have only one access between any two rooms. Now, you want to figure out how many options are available.

Input

The two numbers in the first row represent n and m respectively.

Next n lines, m characters in each line, each character will be '.' or ', where'. 'represents room and' represents column.

Output

An integer in a row indicates the number of legal schemes Mod 10^9

Sample Input

3 3

...

...

.*.

Sample Output

15

HINT

For the first 100%, N, m < = 9

Title Solution

Matrix tree theorem is an open problem, and the elimination element should be divided by rolling.

Code

```
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#define ll long long
#define mod 1000000000
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int xx[]={0,0,1,-1},yy[]={1,-1,0,0};
int n,m,id;
char mp[105][105];
ll a[105][105],ID[105][105];
int det(int n)
{
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++) (a[i][j]+=mod)%=mod;
ll ans=1,f=1;
for (int i=1;i<=n;i++)
{
for (int j=i+1;j<=n;j++)
{
ll A=a[i][i],B=a[j][i];
while (B!=0)
{
ll t=A/B;A%=B;swap(A,B);
for (int k=i;k<=n;k++)
a[i][k]=(a[i][k]-t*a[j][k]%mod+mod)%mod;
for (int k=i;k<=n;k++) swap(a[i][k],a[j][k]);
f=-f;
}
}
if (!a[i][i]) return 0;
ans=ans*a[i][i]%mod;
}
if (f==-1) return (mod-ans)%mod;
return ans;
}
int main()
{
n=read();m=read();
for (int i=1;i<=n;i++) scanf("%s",mp[i]+1);
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
if (mp[i][j]=='.') ID[i][j]=++id;
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)if (ID[i][j])
{
for (int k=0;k<4;k++)
{
int x=i+xx[k],y=j+yy[k];
if (ID[x][y])
{
a[ID[i][j]][ID[i][j]]++;
a[ID[i][j]][ID[x][y]]--;
}
}
}
cout<<det(id-1);
return 0;
}
```