山地图

时间限制:10s      空间限制:128MB

题目描述

一个山地地图是一个n*m的矩阵,每个格点都有一个高度,高度是在1n*m中的一个整数。且没有两个格点高度相同。一个点周围八个点称为与他相邻,一个点比他相邻的点都矮,则称为山谷。
      给定一个地图,地图上表明“X”为山谷,“.”则不是。求这个地图有多少种不同的可能性。答案mod 12345678
数据范围
1<=n<=4
1<=m<=7


输入格式

第一行两个整数nm
接下来n行每行m个字符。


输出格式

 
一个整数表示方案数。


样例输入

1 3
.X.

样例输出

2

提示

没有写明提示


题目来源

没有写明来源