P13450 [GCJ 2009 Finals] Doubly-sorted Grid

如果一个矩形网格的每一行中的字母都从左到右非递减，并且每一列中的字母都从上到下非递减，则称该网格是**双重有序**（doubly sorted）的。下面的例子中，前两个网格是双重有序的，而后两个不是： ``` abc ace aceg base def ade cdef base ghi bdg xxyy base ``` 现在给你一个部分填充的网格，其中有些格子已经填入了字母。你的任务是计算有多少种方式可以填充剩余的格子，使得最终得到的网格是双重有序的。答案可能很大，请输出方案数对 $10007$ 取模后的结果。

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

对于每组测试数据，输出一行，格式如下： Case #$X$: $y$ 其中 $X$ 是测试编号（从 $1$ 开始），$y$ 是方案数对 $10007$ 取模的结果。

**限制条件** - $1 \leq T \leq 40$ - 部分填充的网格中每个字符要么是 '.'，要么是小写英文字母。 **小数据集（10 分）** - 时间限制：5 秒 - $1 \leq R, C \leq 4$ **大数据集（20 分）** - 时间限制：10 秒 - $1 \leq R, C \leq 10$ 翻译由 ChatGPT-4.1 完成。