注意到(4 imes 7)的矩阵的局部极小值最多只有8个，可以状压。
设(f[i][sta])表示从小到大填数，当前填到(i)，极小值的填充状态为(sta)的方案数。
考虑到由于是从小到大填数，每个极小值位置没填时，其四周的位置也不能填。
那么可以分情况讨论：
当前填在极小值位置上，(f[i][sta]+=f[i-1][sta-(1<<j)]).其中(j)为枚举到的位置。
否则，处理出当前状态下可以填的位置数(num)，以前填了(i-1)个，转移：(f[i][sta]+=f[i-1][sta]*(num-(i-1))).
最后的答案为(f[n*m][(1<<num)-1]),(num)为极小值的个数。
但是，可以发现，题目要求极小值只有输入的那几个，但是这样转移可能会在随便填的地方产生新的极小值。
拿这个答案减去多了1个极小值的方案，就可以排除多一个极小值的错误，但是发现多两个的多减了一个，在加上……
其实就是容斥了一下，即原答案(-)多了一个的方案(+)多了两个的方案.....
然后多了几个的方案可以暴力枚举多了哪几个，添加到原图中，然后和上面一样的dp出来。
#include<bits/stdc++.h>
using namespace std;
#define int long long
void read(int &x) {
x=0;int f=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
for(;isdigit(ch);ch=getchar()) x=(x<<1)+(x<<3)+(ch^48);x*=f;
}
void print(int x) {
if(x<0) putchar('-'),x=-x;
if(!x) return ;print(x/10),putchar((x%10)^48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('
');}
const int dx[]={0,1,1,1,0,-1,-1,-1,0};
const int dy[]={0,1,0,-1,1,1,0,-1,-1};
const int mod = 12345678;
int n,m,mp[10][10],f[30][(1<<9)+10],ans,vx[10],vy[10],num[1000],c[5][8];
char s[10];
int check(int x,int y) {return x>=1&&x<=n&&y>=1&&y<=m;}
int calc() {
memset(f,0,sizeof f);f[0][0]=1;vx[0]=0,vy[0]=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(mp[i][j]) vx[++vx[0]]=i,vy[++vy[0]]=j;
for(int s=0;s<(1<<vx[0]);s++) {
memset(c,0,sizeof c);
for(int i=1;i<=vx[0];i++)
if(!(s&(1<<(i-1)))) {
for(int x,y,k=1;k<=8;k++)
if(check(x=vx[i]+dx[k],y=vy[i]+dy[k])) c[x][y]=1;
c[vx[i]][vy[i]]=1;
}num[s]=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
num[s]+=c[i][j]^1;
}
for(int i=1;i<=n*m;i++)
for(int s=0;s<(1<<vx[0]);s++) {
(f[i][s]+=f[i-1][s]*max(0ll,num[s]-(i-1))%mod)%=mod;
for(int j=1;j<=vx[0];j++)
if(s&(1<<(j-1))) f[i][s]=(f[i][s]+f[i-1][s^(1<<(j-1))])%mod;
}
return f[n*m][(1<<vx[0])-1];
}
//void debug() {for(int i=1;i<=n;i++,puts("")) for(int j=1;j<=m;j++,putchar(' ')) printf("%d",mp[i][j]);}
void dfs(int x,int y,int f) {
if(y==m+1) return dfs(x+1,1,f),void();
if(x==n+1) return ans=(ans+calc()*f)%mod,/*debug()*/void();
dfs(x,y+1,f);int flag=0;
for(int i=1;i<=8;i++)
if(check(x+dx[i],y+dy[i])&&mp[x+dx[i]][y+dy[i]]) {flag=1;break;}
if(mp[x][y]) flag=1;
if(!flag) mp[x][y]=1,dfs(x,y+1,-f),mp[x][y]=0;
}
void solve () {
read(n),read(m);
for(int i=1;i<=n;i++) {
scanf("%s",s+1);//cout<<s+1<<endl;
for(int j=1;j<=m;j++) if(s[j]=='X') mp[i][j]=1;
}//debug();puts("");
dfs(1,1,1);write((ans%mod+mod)%mod);
}
signed main() {solve();return 0;}