404688: GYM101608 L Knights

In a custom chess game, you are given an army of r knights placed on a grid. The grid contains r × c cells that are either empty, occupied by a knight, or by an obstacle. Initially, each row has exactly one knight. The knight moves two cells horizontally then one cell vertically, or one cell horizontally then two cells vertically (L-shape moves).

The positions of your knights were leaked, and all of them now have to move to stay safe. Each knight should make exactly one knight-move and jump to an empty cell. Each empty cell can be occupied by at most one knight. Your knights can share the same row after they move. Keep in mind, since all of the old positions of your knights were leaked, it is not safe to use any of these cells again.

Find the number of ways to move all the knights. Two ways are different if the new position of at least one of the knights is different. As the result can be very large, print it modulo 1000000007 (10⁹ + 7).

The first line of input contains a single integer T (1 ≤ T ≤ 256), the number of test cases.

The first line of each test case contains two space-separated integer r and c (3 ≤ r, c ≤ 500), the number of rows and columns, respectively.

Each of the following r lines contains c characters. Each character is one of the following:

• ‘.’: an empty cell.
• '#': a cell that is occupied by an obstacle.
• '*': a cell that is occupied by a knight.

It is guaranteed that each row has exactly one knight.

The total number of knights in all test cases doesn't exceed 10⁵.

For each test case, print the number of ways to move all the knights modulo 10⁹ + 7, on a single line.

3
3 3
*..
..*
..*
3 5
*....
....*
*....
5 5
*..#.
...*.
..#.*
..#.*
*....

2
6
1