[CQOI2012] 局部极小值

题目描述

有一个 $n$ 行 $m$ 列的整数矩阵,其中 $1$ 到 $n\times m$ 之间的每个整数恰好出现一次。 如果一个格子比所有相邻格子(相邻是指有公共边或公共顶点)都小,我们说这个格子是局部极小值。给出所有局部极小值的位置,你的任务是判断有多少个可能的矩阵。 答案对 $12{,}345{,}678$ 取模。

输入输出格式

输入格式


输入第一行包含两个整数 $n$ 和 $m$,即行数和列数。 以下 $n$ 行每行 $m$ 个字符,第 $(i + 1)$ 行的第 $j$ 个字符代表第 $i$ 列的第 $j$ 个格子是否是局部极小值,该字符只可能是 `X` 或 `.`,其中 `X` 表示局部极小值,`.` 表示非局部极小值。

输出格式


输出仅一行,为可能的矩阵总数除以 $12345678$ 的余数。

输入输出样例

输入样例 #1

3 2
X.
..
.X

输出样例 #1

60

说明

#### 数据规模与约定 - 对于 $100\%$ 的数据,保证 $1\le n\le4$,$1\le m\le7$。