To argue, or not to argue

You are the director of a very successful theatre. Above all, you like William Shakespeare, even though he tends toward bloody endings. It was said about some of his plays, like Hamlet and King Lear, that with one more act the killing would have to start in the first rows of the audience.

Right now you are close to holding a grudge against Shakespeare for leaving out that final act. The reason is the 2k celebrities who just arrived at your theatre. They form k pairs of football players, models, and YouTube streamers, and they do not seem to understand what a play is. Each pair is likely to start a heated argument during the show and ruin the performance. You can prevent this by assigning seats. If a pair does not get adjacent seats, a fight is much less likely.

The auditorium has n rows with m seats in each row. Some seats are already booked by normal viewers, and you do not want to move them. Assign a seat to every celebrity so that no pair occupies two adjacent seats. Two seats are adjacent only if they share a side, meaning one is next to or behind the other. Count the ways to do this and output the count modulo $10^9 + 7$. Two assignments differ if any celebrity gets a different seat. All celebrities are distinct.

The first line contains the number of test cases z (1 ≤ z ≤ 100). Each test case starts with a line containing three positive integers n, m, k (1 ≤ $n \cdot m$ ≤ 144, 1 ≤ k ≤ $\frac{mn}{2}$), which are the number of rows, the seats in each row, and the number of celebrity pairs. The next n lines describe the rows. The character 'X' marks an occupied seat that cannot be used, and '.' marks a free seat. You may assume there are at least 2k free seats.

For each test case, output one number on its own line: the number of possible seat assignments such that no pair gets adjacent seats, modulo $10^9 + 7$.

In the first input, all ways of assigning seats are shown below. 'A' and 'a' mark the seats of the first pair, and 'B' and 'b' mark the seats of the second pair.

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