题目描述
大家一定都玩过扫雷这个游戏,如图所示,左上角的数字数字表示地图中
一共有多少雷,右面的数字表示所用的时间,下面的区域已经被翻开一部分,
数字表示在与此方块相连的8个方块中的雷数。
现在给出扫雷区域的高n宽m,以及地图中含有的雷数k,和已知部分。
请计算这些雷的所有排列方式的数目(所有雷都一样)。
由于数目可能很大,所
以只要输出mod 10000(即对1000求余)的结果即可。
0<n,m<=100
0<k<=100
输入格式
第一行 三个整数n,m,k 分别表示扫雷区域的高和宽,地图中含有的雷数。
以下n 行 每行m个字符 表示地图的具体情况。
如果字符为‘0’到‘8’中的,表示此区域已被探索,数字表示周围的雷数。
如果为‘.’则表示此区域未知。
输出格式
一个小于10000的整数 表示这些雷的所有排列方式的数目mod 10000后的结果。
样例输入
样例输出