#P2884. 山地图

    ID: 1991 传统题 1000ms 512MiB 尝试: 20 已通过: 13 难度: 8 上传者: 标签>CF2500提高+/省选-容斥原理子集 DP回溯搜索可行性剪枝位集求并位计数Pascal 递推

山地图

题目描述

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

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

输入格式

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

接下来 nn 行每行 mm 个字符。

输出格式

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

1 3
.X.
2

数据规模与约定

对于 100%100\% 的数据,1≤n≤41\leq n\leq 4,1≤m≤71\leq m\leq 7。