이중 정렬 격자

각 칸에 영어 소문자가 하나씩 적힌 직사각형 격자가 있다. 모든 행에서 글자가 왼쪽에서 오른쪽으로 감소하지 않고, 모든 열에서 글자가 위에서 아래로 감소하지 않으면 이 격자를 이중 정렬 격자라고 부른다. 아래 네 격자 중 앞의 두 개는 이중 정렬 격자이고, 나머지 두 개는 아니다.

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

일부 칸만 채워진 격자가 주어진다. 비어 있는 칸을 모두 채워서 이중 정렬 격자를 만드는 방법이 몇 가지인지 세어라. 답이 매우 커질 수 있으므로 $10007$로 나눈 나머지를 출력한다.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫째 줄에는 행의 수 $R$과 열의 수 $C$가 공백으로 구분되어 주어진다. 다음 $R$개의 줄에는 길이가 $C$인 문자열이 한 줄씩 주어지며, 이것이 일부만 채워진 격자다. 격자의 각 문자는 영어 소문자이거나, 아직 채우지 않은 칸을 뜻하는 '.'이다.

제한

• $1 \le T \le 40$
• $1 \le R, C \le 10$
• 격자의 각 문자는 '.' 또는 영어 소문자다.

각 테스트 케이스마다 한 줄을 출력한다. 그 줄에는 "Case #X: y"를 출력하며, $X$는 1부터 시작하는 테스트 케이스 번호이고 $y$는 만들 수 있는 이중 정렬 격자의 개수를 $10007$로 나눈 나머지다.