Description

如果一个矩形网格的每一行中的字母都从左到右非递减，并且每一列中的字母都从上到下非递减，则称该网格是双重有序（doubly sorted）的。下面的例子中，前两个网格是双重有序的，而后两个不是：

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

现在给你一个部分填充的网格，其中有些格子已经填入了字母。你的任务是计算有多少种方式可以填充剩余的格子，使得最终得到的网格是双重有序的。答案可能很大，请输出方案数对 $10007$ 取模后的结果。

Input Format

输入的第一行是测试用例数 $T$。接下来有 $T$ 组测试数据。每组测试数据的第一行为两个整数 $R$ 和 $C$，分别表示网格的行数和列数。接下来 $R$ 行，每行一个长度为 $C$ 的字符串，表示部分填充的网格。网格中的每个字符要么是小写英文字母，要么是 '.'（表示该格未填）。

Output Format

对于每组测试数据，输出一行，格式如下：

Case #$X$: $y$

其中 $X$ 是测试编号（从 $1$ 开始），$y$ 是方案数对 $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

Hint

限制条件

• $1 \leq T \leq 40$
• 部分填充的网格中每个字符要么是 '.'，要么是小写英文字母。

小数据集（10 分）

• 时间限制：5 秒
• $1 \leq R, C \leq 4$

大数据集（20 分）

• 时间限制：10 秒
• $1 \leq R, C \leq 10$

翻译由 ChatGPT-4.1 完成。