题目描述

The Windows Minesweeper （WinMine） is one of the most well-known games on the Windows system．The rule is quite easy and it takes only a few minutes to play a set．First of all，let’s briefly introduce this game （if you believe that you are familiar enough with this game，you can skip the next paragraph）：

The goal of the game is to uncover all the squares that do not contain mines （with the left mouse button） without being destroyed by clicking on a mine．The location of the mines is discovered by a process of logic．Clicking on the game board will reveal what is hidden underneath the chosen square or squares （a large number of blank squares may be revealed in one go if they are adjacent to each other）．Some squares are blank but some contain numbers （$1$ to $8$），each number being the number of mines adjacent to the uncovered square．The game is won once all blank squares have been uncovered without hitting a mine，any remaining mines not identified by flags being automatically flagged by the computer．The distinctive feature of minesweeper is the randomness at the initial stage and at some intermediate stages．
----Wikipedia

Jaddy loves playing WinMine at free time very much due to its simplicity and ingenuity．However，sometimes it makes him frustrated when he reaches some undeterminable states during the game．See the following state as an example：
In the red circle of this example，the rest two squares are absolutely undeterminable and there are apparently two possible distributions of the rest ONE mine．
When Jaddy gets into this kind of trouble，he has no choice but to guess．Sometimes there are only two possible choices （as what the example says） but sometimes there are many．This way，he needs an assistant of this game to calculate the number of different possible distributions of mines depending on the current state of game board．
This assistant of game is pretty useful and interesting，at least for him，so that he immediately starts coding．Unfortunately，Jaddy spent all the time to play WinMine in the class of Programming and Algorithm，so he feels such a complex task is a mission impossible．Jaddy loves WinMine very much so that he asks you，an excellent programmer，for help．In addition，in order to reduce the difficulty，he added three constraints：

1. It is guaranteed that the input state of game can always be created by making only ONE click on the initial board．
2. In the given state，if two unrevealed squares are connected directly or by any other unrevealed squares，they are also bi-connected．That is to say，even after any one of the other unrevealed squares is removed，these two squares are still connected．Here we say two squares are connected if and only if they share an edge．That means a square has at most four squares connected．
3. In the given state，if two numbers are connected by sharing an edge directly or by other numbers，all the unrevealed cells adjacent to the connected set of numbers must be connected．
   Help Jaddy please！

输入格式

There are multiple test cases，the first line of input is a positive integer $T$ indicating the number of test cases.Then $T$ cases follow．For each test case，the first line contains three positive integers $n,m$ and $M$ denoting the number of rows and columns in the given board and the total number of mines on the board．Then an $n \ast m$ matrix of chars describing the current state of board will be given．In this matrix，there are $2$ styles of symbols：

1. digits from $0$ to $8$：that means the number of mines around this square （0 implies a blank square）．
2. . （quotes for clarifying）： that means this square is unrevealed．

输出格式

For each test case，output an integer leading by the case number，denoting the number of possible distribution of mine in the given state，module by $1000003$．See the sample output for further details．

4 5 2
…..
.....
11111
00000
4 5 4
…..
.....
22222
00000

Case #1: 2
Case #2: 1

数据规模与约定

$100\%$ 的数据满足：$T \le 50,1 \le n,m \le 100,1 \le M \le 1000$。

提示

Notice
(a) The upper bound of $w$ （the number of mines） should be $1500$，rather than $1000$ in the problem statement．
(b) There is another （the third） constraint about the initial state of board：for any pair of unrevealed squares $A$ and $B$，if $A$ and $B$ are both adjacent to a connected component $S$，where $S$ is a connected area consisting of only squares with positive positive positive positive numbers，then $A$ and $B$ can always be connected by unrevealed squares．For example，the following board contradicts this constraint due to the disconnection of squares on row $7$ column $3$ and row $8$ column $4$：

00000001 1 .
11000001..
.1000002..
11000001..
0000000111
0111000000
01.3221100
012....100
0012221100
1100001110
.100001.10

，whereas the following one is acceptable：

..10000000
2210011100
000001.100
000001.100
000011.221
00001.....
01122.....
12........
..........

题目来源

Acm 2011 上海