用的括号序列，听说比较快。
然并不会预处理，只会每回暴力找匹配的括号。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 199917
#define ll long long
#define bp 1<<bit[j-1]
#define bq 1<<bit[j]
using namespace std;
int n,m;
int map[][];
int head[],num,ver[N],nxt[N],tot[],hash[][N];
ll f[][N];
int now,pre;
int bit[];
int edx,edy;
bool ed(int x,int y)
{
return x==edx&&y==edy;
}
void add(int s,ll d)
{
int a=s%;
for(int i=head[a];i;i=nxt[i])
{
if(hash[now][ver[i]]==s)
{
f[now][ver[i]]+=d;
return ;
}
}
tot[now]++;hash[now][tot[now]]=s;
f[now][tot[now]]=d;
num++;nxt[num]=head[a];head[a]=num;ver[num]=tot[now];
return ;
} int main()
{
for(int i=;i<=;i++)bit[i]=*i;
scanf("%d%d",&n,&m);
char s[];
for(int i=;i<=n;i++)
{
scanf("%s",s);
for(int j=;j<=m;j++)
{
if(s[j-]=='*')map[i][j]=;
else map[i][j]=;
}
}
bool flag=;
for(int i=n;i>=;i--)
{
for(int j=m;j>=;j--)
{
if(map[i][j])
{
edx=i,edy=j;break;
}
}
if(edx)break;
}
now=;pre=;
f[now][]=;tot[now]=;hash[now][]=;
for(int i=;i<=n;i++)
{
for(int j=;j<=tot[now];j++)hash[now][j]<<=;
for(int j=;j<=m;j++)
{
now^=;pre^=;
memset(head,,sizeof(head));
memset(f[now],,sizeof(f[now]));
tot[now]=;num=;
for(int k=;k<=tot[pre];k++)
{
int s=hash[pre][k];ll d=f[pre][k];
if(!d)continue;
int p=(s/(bp))&,q=(s/(bq))&;
if(!map[i][j])
{
if(!p&&!q)add(s,d);
}
else if(!p&&!q)
{
if(j<m)add(s^(bp)^(bq+),d);
}
else if(!p)
{
if(q==)
{
add(s^(bq)^(bp),d);
if(j<m)add(s,d);
}
else
{
add(s^(bq+)^(bp+),d);
if(j<m)add(s,d);
}
}
else if(!q)
{
if(p==)
{
if(j<m)add(s^(bp)^(bq),d);
add(s,d);
}
else
{
if(j<m)add(s^(bq+)^(bp+),d);
add(s,d);
}
}
else if(p==)
{
if(q==)add(s^(bp+)^(bq),d);
else
{
int dd=;
for(int l=j-;l>=;l--)
{
if(((s>>bit[l])&)==)dd++;
else if(((s>>bit[l])&)==)dd--;
if(!dd)
{
add((s^(bp+)^(bq+))-(<<bit[l])+(<<bit[l]+),d);
break;
}
}
}
}
else if(p==)
{
if(q==)
{
if(ed(i,j))add(s^(bp)^(bq+),d);
}
else
{
int ss=s>>bit[j+],dd=;
for(int l=j+;l<=m;l++,ss>>=)
{
if((ss&)==)dd++;
else if((ss&)==)dd--;
if(!dd)
{
add((s^(bp)^(bq))-(<<bit[l]+)+(<<bit[l]),d);
break;
}
}
}
}
}
}
}
ll ans=;
for(int i=;i<=tot[now];i++)
{
if(hash[now][ver[i]]==)ans=f[now][ver[i]];
}
printf("%lld\n",ans);
return ;
}