Doubly Sorted Grid

A rectangular grid with one lowercase English letter in each cell is doubly sorted if the letters in every row are non-decreasing from left to right and the letters in every column are non-decreasing from top to bottom. Among the four grids below, the first two are doubly sorted and the other two are not.

abc    ace    aceg    base
def    ade    cdef    base
ghi    bdg    xxyy    base

You are given a grid in which only some of the cells are filled. Count the ways to fill every empty cell so that the result is a doubly sorted grid. The answer can be large, so print it modulo $10007$.

The first line contains the number of test cases $T$. Then $T$ test cases follow. The first line of each test case contains two integers $R$ and $C$, the number of rows and the number of columns. The next $R$ lines each contain a string of length $C$ that gives the partially filled grid. Each character of the grid is either a lowercase English letter or '.', which marks a cell that is not filled yet.

Limits

• $1 \le T \le 40$
• $1 \le R, C \le 10$
• Each character of the grid is '.' or a lowercase English letter.

Print one line for each test case. The line contains "Case #X: y", where $X$ is the test case number starting from 1 and $y$ is the number of possible doubly sorted grids modulo $10007$.