이중 정렬 격자 (작은 입력)

문제

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

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 4$
격자의 각 문자는 . 또는 영어 소문자다.

출력

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