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 (109 + 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:
It is guaranteed that each row has exactly one knight.
The total number of knights in all test cases doesn't exceed 105.
For each test case, print the number of ways to move all the knights modulo 109 + 7, on a single line.
## Input
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 105.
## Output
For each test case, print the number of ways to move all the knights modulo 109 + 7, on a single line.
[samples]
**Definitions**
Let $ T \in \mathbb{Z} $ be the number of test cases.
For each test case:
- Let $ r, c \in \mathbb{Z} $ denote the number of rows and columns, respectively.
- Let $ G \in \{ \text{'.', 'K', '#' } \}^{r \times c} $ be the grid, where:
- `'.'` denotes an empty cell,
- `'K'` denotes a knight,
- `'#'` denotes an obstacle.
- Let $ K = \{ (i, j) \mid G[i][j] = \text{'K'} \} $ be the set of initial knight positions, with $ |K| = r $ and exactly one knight per row.
Let $ M : K \to \mathcal{P}(\mathbb{Z}^2) $ map each knight at $ (i, j) $ to the set of valid target cells reachable by a knight-move:
$$
M(i,j) = \left\{ (i', j') \in [0, r-1] \times [0, c-1] \,\middle|\,
\begin{array}{c}
(i' - i, j' - j) \in \{ (\pm1, \pm2), (\pm2, \pm1) \} \\
G[i'][j'] = \text{'.'} \\
(i', j') \notin K
\end{array}
\right\}
$$
**Constraints**
1. $ 1 \le T \le 256 $
2. $ 3 \le r, c \le 500 $
3. Each row contains exactly one knight.
4. Total knights across all test cases $ \le 10^5 $
**Objective**
Compute the number of injective functions $ f : K \to \bigcup_{(i,j) \in K} M(i,j) $ such that $ f(i,j) \in M(i,j) $ for all $ (i,j) \in K $, modulo $ 10^9 + 7 $.
That is, count the number of perfect matchings from knights to valid target cells under the constraint that no two knights move to the same cell.