이중 정렬된 격자

각 칸에 소문자 영문자가 있는 직사각형 격자에서, 각 행의 문자가 왼쪽에서 오른쪽으로 갈수록 감소하지 않고 각 열의 문자가 위에서 아래로 갈수록 감소하지 않으면 이 격자를 이중 정렬되었다고 한다. 다음 예제에서 처음 두 격자는 이중 정렬되어 있지만, 나머지 두 격자는 그렇지 않다:

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

일부 칸이 문자로 채워진 격자가 주어진다. 나머지 칸을 채워서 결과 격자가 이중 정렬되도록 하는 방법의 수를 계산해야 한다. 답은 큰 수일 수 있으므로, 방법의 수를 10007로 나눈 나머지를 출력해야 한다.

제한

메모리 제한: 1 GB. 1 ≤ T ≤ 40 일부만 채워진 격자의 각 문자는 '.' 또는 소문자 영문자이다.

작은 데이터 세트

시간 제한: 60초. 1 ≤ R, C ≤ 4

큰 데이터 세트

시간 제한: 120초. 1 ≤ R, C ≤ 10

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 각각 행의 수와 열의 수를 나타내는 두 정수 R과 C가 포함된 한 줄로 시작한다. 이어서 각각 길이가 C인 문자열을 포함하는 R개의 줄에 일부만 채워진 격자가 주어진다. 격자의 각 문자는 소문자 영문자이거나, 해당 칸이 아직 채워지지 않았음을 나타내는 '.'이다.

각 테스트 케이스마다 한 줄을 출력한다. 그 줄에는 "Case #X: y"을 출력한다. 여기서 X는 1부터 시작하는 케이스 번호이고, y는 가능한 이중 정렬된 격자의 수를 10007로 나눈 나머지이다.