#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second #define m_p make_pair #define p_b push_back using namespace std; typedef long long ll; const int maxn=1e6+10; inline ll read(){ ll x=0;short t=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } int n,m; string s[1005]; const int dx[]={0,0,1,-1}; const int dy[]={1,-1,0,0}; struct dsu { int fa[maxn],siz[maxn]; stack<pi>S; int fd(int x){ if(x==fa[x])return x; return fd(fa[x]); }void init(){ up(i,1,n*m)fa[i]=i,siz[i]=1; }int merge(int x,int y){ x=fd(x),y=fd(y); if(x==y)return 0; if(siz[x]>siz[y])swap(x,y); fa[x]=y,siz[y]+=siz[x]; S.push(m_p(x,y));return 1; }void rvk(){ auto it=S.top();S.pop(); int x=it.p1,y=it.p2;fa[x]=x,siz[y]-=siz[x]; } }T; int gid(int i,int j){return (i-1)*m+j;} #define ppc __builtin_popcount int tag[1005][1005]; int gen(int i,int j){ int c=0; up(k,0,3){ int ni=i+dx[k],nj=j+dy[k]; if(ni<1||ni>n||nj<1||nj>m||s[ni][nj]=='#')continue; c+=T.merge(gid(i,j),gid(ni,nj)); }return c; } void slv(){ n=read(),m=read();up(i,1,n)cin>>s[i],s[i]=" "+s[i]; T.init(); up(i,1,n){ up(j,1,m){ if(s[i][j]=='#')continue; up(k,0,3){ int ni=i+dx[k],nj=j+dy[k]; if(ni<1||ni>n||nj<1||nj>m||s[ni][nj]=='#')continue; T.merge(gid(i,j),gid(ni,nj)); } } } int ct=0;up(i,1,n)up(j,1,m)if(s[i][j]=='#')ct++; if(T.fd(gid(1,1))==T.fd(gid(n,m))){ cout<<ct*1ll*(ct-1)/2;return; } ll res=0,ret=0; int cc=0; map<vector<int>,int>mp; vector<vector<int> >Q; up(i,1,n){ up(j,1,m){ if(s[i][j]!='#')continue; int c=gen(i,j); if(T.fd(gid(1,1))==T.fd(gid(n,m))){ tag[i][j]=1,cc++; while(c--)T.rvk(); } else if(T.fd(gid(i,j))==T.fd(gid(1,1))){ while(c--)T.rvk(); vector<int>E; up(k,0,3){ int ni=i+dx[k],nj=j+dy[k]; if(ni<1||ni>n||nj<1||nj>m||s[ni][nj]=='#')continue; E.p_b(T.fd(gid(ni,nj))); }sort(E.begin(),E.end()),E.erase(unique(E.begin(),E.end()),E.end()); int w=E.size(); up(i,1,(1<<w)-1){ vector<int>S; up(j,0,w-1)if((i>>j)&1)S.p_b(E[j]); mp[S]++; } }else if(T.fd(gid(i,j))==T.fd(gid(n,m))){ while(c--)T.rvk(); vector<int>E; up(k,0,3){ int ni=i+dx[k],nj=j+dy[k]; if(ni<1||ni>n||nj<1||nj>m||s[ni][nj]=='#')continue; E.p_b(T.fd(gid(ni,nj))); }sort(E.begin(),E.end()),E.erase(unique(E.begin(),E.end()),E.end()); Q.p_b(E); }else while(c--)T.rvk(); } } ret=cc*1ll*(cc-1)/2+cc*1ll*(ct-cc); //cout<<"ret:"<<cc<<" "<<ret<<endl; for(auto it:Q){ int sz=it.size(); up(j,1,(1<<sz)-1){ vector<int>A; up(k,0,sz-1)if((j>>k)&1)A.p_b(it[k]); if(mp.count(A))res+=mp[A]*((ppc(j)&1)?1:-1); } } int other=0; up(i,1,n){ up(j,1,m){ if(s[i][j]!='#'||tag[i][j])continue; vector<int>E; up(k,0,3){ int ni=i+dx[k],nj=j+dy[k]; if(ni<1||ni>n||nj<1||nj>m||s[ni][nj]=='#')continue; E.p_b(T.fd(gid(ni,nj))); }sort(E.begin(),E.end()),E.erase(unique(E.begin(),E.end()),E.end()); up(k,0,3){ int ni=i+dx[k],nj=j+dy[k]; if(ni<1||ni>n||nj<1||nj>m||s[ni][nj]!='#'||tag[ni][nj])continue; set<int>S; up(k,0,3){ int nii=ni+dx[k],njj=nj+dy[k]; if(nii<1||nii>n||njj<1||njj>m||s[nii][njj]=='#')continue; S.insert(T.fd(gid(nii,njj))); } //cout<<"test "<<i<<" "<<j<<" "<<ni<<" "<<nj<<endl; bool ok=0; for(int x:E)if(S.count(x))ok=1; if(ok)continue; //cout<<"test "<<i<<" "<<j<<" "<<ni<<" "<<nj<<endl; int c=gen(i,j); c+=T.merge(gid(i,j),gid(ni,nj)); c+=gen(ni,nj); if(T.fd(gid(1,1))==T.fd(gid(n,m))){ other++; }while(c--)T.rvk(); } } } cout<<res+ret+other/2; }int main(){ //freopen("room.in","r",stdin); //freopen("room.out","w",stdout); slv(); fclose(stdin); fclose(stdout); return 0; }