Market Board (Large)

While climbing Jirisan you stop at a market day. In one corner of the crowd somebody is running a game.

The game uses a grid board of $N$ rows and $M$ columns on a table. Every cell of the grid holds one $K$-sided die.

The host fixes some of the dice so that a chosen face shows and leaves the rest loose. The board is then shaken, and every die that is not fixed, called a free die, comes to rest showing one of its $K$ faces. Each face shows with the same probability $1/K$, and the dice are independent of each other.

Once the board stops, every cell is scored. Four directions count: horizontal, vertical, and the two diagonals. A cell is scored like this.

1. If some run of four consecutive cells in one direction contains this cell and all four show the same face, the cell scores $S_4$.
2. Otherwise, if some run of three consecutive cells in one direction contains this cell and all three show the same face, the cell scores $S_3$.
3. Otherwise, if some run of two consecutive cells in one direction contains this cell and both show the same face, the cell scores $S_2$.
4. Otherwise the cell scores 0.

The score of the game is the sum of the scores of all cells.

The dice have been fixed and the board is about to be shaken. Compute the expected score of the game.

The first line has the number of test cases $T$.

The first line of each test case has six integers $N$, $M$, $K$, $S_4$, $S_3$, $S_2$ separated by spaces. $N$ is the number of rows of the board, $M$ is the number of columns, and $K$ is the number of faces of a die. $S_4$, $S_3$ and $S_2$ are the scores described above.

The next $N$ lines give the rows of the board from the top row down. Each line is a string of length $M$ and gives the state of the dice in that row from the left. A fixed die is written as a single digit from 1 to $K$, the number of the face it shows. A free die is written as a question mark ?.

Limits

• $1 \le T \le 50$
• $2 \le N \le 100$, $2 \le M \le 100$
• $2 \le K \le 9$
• $0 \le S_2 \le S_3 \le S_4 \le 100$
• There is no limit on the number of free dice.

For each test case print one line of the form Case #x: y, where $x$ is the test case number starting at 1 and $y$ is the expected score of that case. Round $y$ to seven digits after the decimal point and print exactly seven digits after the point.