题目描述

A rectangular grid with lower case English letters in each cell is called doubly sorted if in each row the letters are non-decreasing from the left to the right, and in each column the letters are non-decreasing from the top to the bottom. In the following examples, the first two grids are doubly sorted, while the other two are not:

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

You are given a partially-filled grid, where some of the cells are filled with letters. Your task is to compute the number of ways you can fill the rest of the cells so that the resulting grid is doubly sorted. The answer might be a big number; you need to output the number of ways modulo $10007$.

输入格式

The first line of input gives the number of test cases, $T$. $T$ test cases follow. Each test case starts with a line containing two integers $R$ and $C$, the number of rows and the number of columns respectively. This is followed by $R$ lines, each containing a string of length $C$, giving the partially-filled grid. Each character in the grid is either a lower-case English letter, or '.', indicating that the cell is not filled yet.

输出格式

For each test case, output one line. That line should contain "Case #$X$: $y$", where $X$ is the case number starting with 1, and $y$ is the number of possible doubly-sorted grids, modulo $10007$.

3
2 2
ad
c.
3 3
.a.
a.z
.z.
4 4
....
.g..
.cj.
....

Case #1: 23
Case #2: 7569
Case #3: 0

提示

Limits

• $1 \leq T \leq 40$
• Each character in the partially-filled grid is either '.' or a lower-case English letter.

Small dataset(10 Pts)

• Time limit: 60 5 seconds.
• $1 \leq R, C \leq 4$

Large dataset(20 Pts)

• Time limit: 120 10 seconds.
• $1 \leq R, C \leq 10$