[cqoi2012]局部极小值

时间限制:3s    【提交】    空间限制:128MB

题目描述

有一个nm列的整数矩阵,其中1到nm之间的每个整数恰好出现一次。如果一个格子比所有相邻格子(相邻是指有公共边或公共顶点)都小,我们说这个格子是局部极小值。
给出所有局部极小值的位置,你的任务是判断有多少个可能的矩阵。


输入格式

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


输出格式

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


样例输入

3 2
X.
..
.X

样例输出

60

提示

没有写明提示


题目来源

没有写明来源