Winmine (Minesweeper)

Minesweeper (Winmine) is one of the best-known games bundled with Windows. The rules are simple: you win by uncovering every square that does not contain a mine, and you lose the moment you uncover a mine.

Uncovering a square reveals what is hidden beneath it. Some squares are blank (no mine in the surrounding area), while others show a number from 1 to 8; that number is the count of mines among the eight squares adjacent to it. Uncovering a blank square (the number 0) causes its adjacent blank squares to be uncovered in a chain.

Jaddy enjoys the game, but he sometimes reaches a state where the location of the mines cannot be determined by logic alone. The figure below shows such a case.

Inside the red circle, the two remaining squares are impossible to determine, and there are clearly two ways to place the single remaining mine.

In situations like this a player has no choice but to guess. So Jaddy wants a tool that, given the current state of the board, counts the number of distinct ways the mines can be distributed. Help him out.

To make the task easier, the input is guaranteed to satisfy the following two conditions.

1. The given board state can always be produced by making exactly one click on the initial board.
2. For the unrevealed squares, if two of them are connected (directly or through other unrevealed squares), then they are biconnected. That is, even after removing any single one of the other unrevealed squares, those two squares remain connected. Here two squares are connected if and only if they share an edge, so a square is connected to at most four squares.

The input consists of several test cases. The first line contains a positive integer $T$ ($T \le 50$), the number of test cases. Then $T$ test cases follow.

The first line of each test case contains three positive integers $n$, $m$, and $w$ ($1 \le n, m \le 100$, $1 \le w \le 1000$), where $n$ and $m$ are the number of rows and columns of the board and $w$ is the total number of mines on the board.

The next lines contain an $n \times m$ grid of characters describing the current board state. Each character is one of the following.

• a digit 0 to 8: the number of mines among the eight squares adjacent to this square (0 means a blank square with no adjacent mine).
• . (a dot): an unrevealed square.

For each test case, print a single line in the form Case #k: X, where $k$ is the test-case number (starting from 1) and $X$ is the number of distinct ways the mines can be distributed in the given state, taken modulo $1000003$.