嘟嘟嘟
谁说CQOI的题都是板儿题，我就觉得这题挺难的……
看到数据范围这么小，就会想状压。然而(2 ^ {28})肯定过不了。不过对于所有的极小值的格子，最多不会超过8个，所以我们状压选了哪些局部极小值的格子（坑儿）。
然后我们从小到大填数，那么对于一个数(i)，他无非就两种填法：填入一个坑，或是填坑以外的点。
填一个坑儿就是直接填，于是有(dp[i][S] = sum dp[i - 1][S) ^ ((1 << k)])。
不填坑的话，得考虑填上这个数之后，那些还没有填的坑仍能保证是坑，即不能往他们的四周填。因此我们预处理出来对于当前每一个状态，可以填的格子数目(num[S])。然后有转移方程(dp[i][S] = dp[i - 1][S] * (num[S] - (i - 1)))。
答案就是(dp[n * m][(1 << tot) - 1])，(tot)是坑的总数。
但光这样是不对的。因为一些不是坑的点填完后可能成为了坑，换句话说，我们上面的(dp[n * m][(1 << tot) -1])表示的是至少有(tot)个坑时的方案数，而我么需要的是恰好有这么多坑的方案数。
那么就能想到容斥了！我们暴力枚举棋盘上哪些格子可以是坑，然后每构造一个棋盘，就dp一次，然后看看是加上还是减去。
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<vector>
#include<stack>
#include<queue>
#include<assert.h>
using namespace std;
#define enter puts("")
#define space putchar(' ')
#define Mem(a, x) memset(a, x, sizeof(a))
#define In inline
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-8;
const ll mod = 12345678;
In ll read()
{
ll ans = 0;
char ch = getchar(), last = ' ';
while(!isdigit(ch)) last = ch, ch = getchar();
while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
if(last == '-') ans = -ans;
return ans;
}
In void write(ll x)
{
if(x < 0) x = -x, putchar('-');
if(x >= 10) write(x / 10);
putchar(x % 10 + '0');
}
In void MYFILE()
{
#ifndef mrclr
freopen(".in", "r", stdin);
freopen(".out", "w", stdout);
#endif
}
int n, m, TOT;
char s[5][8];
ll ans = 0;
In ll inc(ll a, ll b) {return a + b < mod ? a + b : a + b - mod;}
struct Node
{
int x, y;
}t[30];
int tot = 0, num[(1 << 8) + 5];
bool vis[5][8];
ll dp[30][(1 << 8) + 5];
const int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1}, dy[] = {0, 1, 1, 1, 0, -1, -1, -1};
In void calc()
{
tot = 0;
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j)
if(s[i][j] == 'X') t[++tot] = (Node){i, j};
for(int i = 0; i < (1 << tot); ++i)
{
Mem(vis, 0);
for(int j = 1; j <= tot; ++j)
if(!((i >> (j - 1)) & 1))
{
vis[t[j].x][t[j].y] = 1;
for(int k = 0; k < 8; ++k)
{
int nx = t[j].x + dx[k], ny = t[j].y + dy[k];
if(nx && nx <= n && ny && ny <= m) vis[nx][ny] = 1;
}
}
int cnt = 0;
for(int j = 1; j <= n; ++j)
for(int k = 1; k <= m; ++k) cnt += vis[j][k];
num[i] = n * m - cnt;
}
Mem(dp, 0); dp[0][0] = 1;
for(int i = 1; i <= n * m; ++i)
{
for(int S = 0; S < (1 << tot); ++S)
{
dp[i][S] = inc(dp[i][S], dp[i - 1][S] * (num[S] - i + 1) % mod);
for(int j = 0; j < tot; ++j)
if((S >> j) & 1) dp[i][S] = inc(dp[i][S], dp[i - 1][S ^ (1 << j)]);
}
}
ll tp = dp[n * m][(1 << tot) - 1];
ans = inc(ans, ((tot - TOT) & 1) ? mod - tp: tp);
}
In void dfs(int x, int y)
{
if(x == n + 1) {calc(); return;}
if(y == m) dfs(x + 1, 1);
else dfs(x, y + 1);
if(s[x][y] == 'X') return;
bool flg = 1;
for(int i = 0; i < 8 && flg; ++i)
{
int nx = x + dx[i], ny = y + dy[i];
if(nx && nx <= n && ny && ny <= m)
if(s[nx][ny] == 'X') flg = 0;
}
if(!flg) return;
s[x][y] = 'X';
if(y == m) dfs(x + 1, 1);
else dfs(x, y + 1);
s[x][y] = '.';
}
int main()
{
//MYFILE();
n = read(), m = read();
for(int i = 1; i <= n; ++i) scanf("%s", s[i] + 1);
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j) TOT += (s[i][j] == 'X');
dfs(1, 1);
write(ans), enter;
return 0;
}