题目描述

一个山地地图是一个 $n\times m$ 的矩阵，每个格点都有一个高度，高度是在 $1$ 到 $n\times m$ 中的一个整数。且没有两个格点高度相同。一个点周围八个点称为与他相邻，一个点比他相邻的点都矮，则称为山谷。

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

输入格式

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

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

输出格式

一行一个整数表示答案对 $12345678$ 取模后的值。

1 3
.X.

2

数据规模与约定

对于 $100\%$ 的数据，$1\leq n\leq 4$，$1\leq m\leq 7$。