Cycles in a Maze

Jahid's elder brother Jadu makes fun of Jahid by calling him dumb. So to make Jadu realize about his creativity Jahid created a maze with characters "|", "-", "*", " " and "0" like below:

*-*-*
|0 0|
*-*-*
|0|0|
*-*-*

Here Jahid defines "*" as wooden platforms, "-" and "|" as bridges that horizontally and vertically connect some or no wooden platforms respectively, " "(Space) as a missing platform or a missing bridge and "0" for the sake of indentation which means empty space. So, the above image contains 9 wooden platforms and 11 bridges with 1 missing bridge.

Jahid asks Jadu how many cyclic paths are there in this maze. Cyclic paths start and end on the same platform visiting one or more other platforms using bridges. All platforms other than the starting platform can be visited only once. Also, bridges can be used only once.

Jadu instantly told the answer to be 7 and with an evil laugh in his face, Jadu asked Jahid what will be the answer if any number of this same maze would have been joined together horizontally. Please help Jahid answer this question.

Input

The first line of input contains the number of test cases $T$ ($1 ≤ T ≤ 100$). The first line of each test case contains three integers $N$, $M$, $Q$ ($1 ≤ N ≤ 10$, $1 ≤ M ≤ 100$, $1 ≤ Q ≤ 10^{18}$) where $N$ is the number of rows of platforms, $M$ is the number of columns of platforms and $Q$ is the number of mazes to join together.

The next $2N-1$ lines describe the Maze. All of these lines contain $2M-1$ characters containing only “|”, “-”, “*“, ” “ and “0”. To make the joining strong, borders of the initial maze will not contain any missing platforms or missing bridges.

Output

For each test case, print the number of cyclic paths possible after joining the mazes together modulo $10^9+7$.

Sample

Input	Output
2 3 3 1 *-*-* |0 0| *-*-* |0|0| *-*-* 2 2 2 *-* |0| *-*	7 3
The seven possible cyclic paths of the first sample can be seen below: *-*-* *-*-* *-*-* *-*-* |0 0| |0 0| |0 0| |0 0| 0 0 0 0 0 0 *-*-* * * *-* * * *-* *-*-* *-* *-* 0 0 |0 0| 0|0| |0|0 |0|0| 0|0| |0|0 *-*-* *-* *-* *-*-* *-* *-* Notice how the joining works from the 2nd case. During joining the leftmost column of the new maze overlaps with the rightmost column from the last maze. So the final maze looks like this. *-*-* |0|0| *-*-*