#2669. [cqoi2012]局部极小值

题目描述

有一个 n 行 m 列的整数矩阵，其中1到 nm 之间的每个整数恰好出现一次。如果一个格子比所有相邻格子（相邻是指有公共边或公共顶点）都小，我们说这个格子是局部极小值。

给出所有局部极小值的位置，你的任务是判断有多少个可能的矩阵。

输入格式

输入第一行包含两个整数 n 和 m （1<= n <=4, 1<= m <=7），即行数和列数。以下 n 行每行 m 个字符，其中"X"表示局部极小值，"."表示非局部极小值。

输出格式

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

样例

样例输入

3 2  

X.  

..  

.X  

样例输出

60

数据范围与提示