{"raw_statement":[{"iden":"statement","content":"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).\n\nThe 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.\n\nFind 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).\n\nThe first line of input contains a single integer T (1 ≤ T ≤ 256), the number of test cases.\n\nThe 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.\n\nEach of the following r lines contains c characters. Each character is one of the following:\n\nIt is guaranteed that each row has exactly one knight.\n\nThe total number of knights in all test cases doesn't exceed 105.\n\nFor each test case, print the number of ways to move all the knights modulo 109 + 7, on a single line.\n\n"},{"iden":"input","content":"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."},{"iden":"output","content":"For each test case, print the number of ways to move all the knights modulo 109 + 7, on a single line."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case:  \n- Let $ r, c \\in \\mathbb{Z} $ denote the number of rows and columns, respectively.  \n- Let $ G \\in \\{ \\text{'.', 'K', '#' } \\}^{r \\times c} $ be the grid, where:  \n  - `'.'` denotes an empty cell,  \n  - `'K'` denotes a knight,  \n  - `'#'` denotes an obstacle.  \n- 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.  \n\nLet $ 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:  \n$$\nM(i,j) = \\left\\{ (i', j') \\in [0, r-1] \\times [0, c-1] \\,\\middle|\\, \n\\begin{array}{c}\n(i' - i, j' - j) \\in \\{ (\\pm1, \\pm2), (\\pm2, \\pm1) \\} \\\\\nG[i'][j'] = \\text{'.'} \\\\\n(i', j') \\notin K\n\\end{array}\n\\right\\}\n$$\n\n**Constraints**  \n1. $ 1 \\le T \\le 256 $  \n2. $ 3 \\le r, c \\le 500 $  \n3. Each row contains exactly one knight.  \n4. Total knights across all test cases $ \\le 10^5 $  \n\n**Objective**  \nCompute 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 $.  \n\nThat 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.","simple_statement":"You are given an r×c grid with exactly one knight in each row. Knights move in L-shapes (like chess knights). All knights must move exactly once to an empty cell (not their original position), and no two knights can land on the same cell. Count the number of ways to do this, modulo 1000000007.","has_page_source":false}