山地图

一个山地地图是一个 $n\times m$ 的矩阵，每个格点都有一个高度，高度是在 $1$ 到 $nm$ 中的一个整数，且没有两个格点高度相同。

一个点周围的八个点称为与它相邻。如果一个点比它相邻的点都矮，则称为山谷。

给定一个地图，地图上表明 X 为山谷，. 则不是。求这个地图有多少种不同的可能性，答案对 $12345678$ 取模。

输入格式

第一行两个整数 $n, m$。

接下来 $n$ 行，每行 $m$ 个字符。

输出格式

一个整数，表示方案数。

样例输入

1 3
.X.

样例输出

2

数据范围

• $1\le n\le 4$；
• $1\le m\le 7$。

来源与许可

本题题面与测试数据整理自 BZOJ 2884。

样例 1

输入

1 3
.X.

输出

2