如果一个矩形网格的每个单元格中都填有小写英文字母，且满足每一行从左到右字母非递减，每一列从上到下字母非递减，则称该网格为“双重有序”的。在以下示例中，前两个网格是双重有序的，而后两个不是：

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

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

输出格式 1

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