싸울 것인가, 말 것인가

당신은 아주 성공적인 극장의 감독입니다. 무엇보다 셰익스피어를 좋아하지만, 그의 작품이 피비린내 나는 결말로 치닫는 경향은 못마땅합니다. 『햄릿』이나 『리어왕』 같은 작품은 막이 하나만 더 있었다면 앞줄 관객부터 살해가 시작되었을 것이라는 말이 있습니다.

지금 당신은 셰익스피어가 마지막 막을 넣지 않은 것 때문에 원망이 생기려 합니다. 이유는 방금 극장에 도착한 2k명의 유명인입니다. 이들은 축구 선수, 모델, 유튜브 스트리머로 이루어진 k쌍이며, 연극이 무엇인지 제대로 이해하지 못하는 것 같습니다. 각 쌍은 공연 중에 열띤 말다툼을 벌여 공연을 망가뜨릴 가능성이 높습니다. 그래도 좌석을 배정하면 막을 수 있습니다. 쌍이 서로 인접하지 않은 좌석에 앉으면 싸움이 일어날 가능성이 훨씬 낮아집니다.

관람석은 n개의 행과 행마다 m개의 좌석으로 이루어집니다. 일반 관객이 이미 예매한 좌석이 있으며, 이들의 자리는 옮기지 않습니다. 어떤 쌍도 인접한 두 좌석을 차지하지 않도록 모든 유명인에게 좌석을 배정하세요. 두 좌석은 변을 공유할 때만 인접한 것으로 봅니다. 즉 한 좌석이 다른 좌석의 바로 옆이나 바로 뒤에 있을 때입니다. 가능한 배정의 수를 세어 $10^9 + 7$로 나눈 나머지를 구하세요. 어떤 유명인이라도 다른 좌석을 받으면 서로 다른 배정으로 봅니다. 모든 유명인은 서로 구별됩니다.

첫 줄에 테스트 케이스의 수 z (1 ≤ z ≤ 100)가 주어집니다. 각 테스트 케이스의 첫 줄에는 양의 정수 n, m, k (1 ≤ $n \cdot m$ ≤ 144, 1 ≤ k ≤ $\frac{mn}{2}$)가 주어집니다. 이는 각각 행의 수, 한 행의 좌석 수, 유명인 쌍의 수입니다. 이어서 n개의 줄이 각 행을 나타냅니다. 'X'는 사용할 수 없는 좌석, '.'은 빈 좌석입니다. 빈 좌석은 적어도 2k개 있다고 가정해도 됩니다.

각 테스트 케이스마다 어떤 쌍도 인접한 좌석을 받지 않는 배정의 수를 $10^9 + 7$로 나눈 나머지를 한 줄에 하나씩 출력하세요.

첫 번째 입력에서 가능한 배정을 모두 나타내면 다음과 같습니다. 'A'와 'a'는 첫 번째 쌍, 'B'와 'b'는 두 번째 쌍의 좌석입니다.

 AB   Ab   ab   aB   BA   bA   ba   Ba
 ba   Ba   BA   bA   ab   aB   AB   Ab