题目描述

一天，maze决定对自己的一块n*m的土地进行修建。他希望这块土地共n*m个格子的高度分别是1,2,3,...,n*m-1,n*m。maze又希望能将这一些格子中的某一些拿来建蓄水池，即这个格子的高度应该比它周围8个格子的高度都小（超出土地范围的格子的高度算作无穷大）。现在，请你帮maze计算：他有多少种不同的修建土地的方案数？
（请你将方案数对12345678取模）

输入格式：

输入第一行两个数字n,m。
接下来N行，每行M个字符，’.’表示普通格子，’X’表示蓄水池。

输出格式：

仅一行，包含一个数字，为取模后的方案数。

输入样例#1：

1 3
.X.

输出样例#1：

2