1828: 扫雷

刚刚参加完期末考试，小X就踏上了JSOI的冬令营之旅，在开往镇江的公交车上。小X发现很多同学都在看车上的《非2》。可惜小X对这部电影不感兴趣，于是百无聊赖的他拿出电脑玩起了自己唯一感兴趣的扫雷游戏。相信大家一定都玩过扫雷这个游戏，游戏的界面如图所示，左上角的数字表示地图中一共有多少雷，右面的数字表示所用的时间，下面的区域已经被翻开一部分,数字表示在与此方块相邻的8个方块中的雷数。由于小X已经是扫雷高手中的高手，所以他对如何排雷已经提不起兴趣，而对雷的排布方式产生了兴趣。现在给出扫雷区域的高n宽m，以及地图中含有的雷数k，和已知部分。现在请你帮助小X计算这些雷所有排布方式的数目。由于数目可能很大，所以只要输出mod 10000的结果即可。

第一行 三个整数n,m,k 分别表示扫雷区域的高和宽，地图中含有的雷数。

以下n行 每行m个字符表示地图的具体情况。

如果字符为‘0’到‘8’中的，表示此区域已被探索，数字表示周围的雷数。

如果为‘.’则表示此区域未知。

一个小于10000的整数 表示这些雷的所有排布方式的数目mod 10000后的结果。

9 9 10
.10000000
110012321
00002....
00002....
00001....
00011....
1101.....
.101122..
1100001..

24