Doubly-sorted grid (small)

A rectangular grid holds one lower case English letter in each cell. The grid 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. Of 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 the remaining cells so that the whole grid is doubly sorted. The answer can be large, so print the number of ways 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 the number of rows $R$ and the number of columns $C$, separated by a space. The next $R$ lines each contain a string of length $C$, and those strings describe the partially filled grid. Each character of the grid is either a lower case English letter or ., which marks a cell that is not filled yet.

Limits

• $1 \le T \le 40$
• $1 \le R, C \le 4$
• Each character of the grid is . or a lower case English letter.

For each test case, print one line in the format Case #X: y, where $X$ is the test case number starting from 1 and $y$ is the number of doubly sorted grids you can obtain, modulo $10007$.