P15060 Crossing Pawn

It is recommended to be rated Brown.

Yuki has a chessboard with $(n+2)$ rows and $(m+2)$ columns. The row indices are $0 \sim n+1$, and the column indices are $0 \sim m+1$. The cell in row $i$ and column $j$ is denoted by $(i,j)$. Each cell can be either white or black, denoted by $s_{i,j}$. If $s_{i,j}=\texttt0$, it is white; if $s_{i,j}=\texttt1$, it is black. **It is guaranteed that the outermost ring of the board is white**, i.e., $s_{0,i}=s_{n+1,i}=s_{i,0}=s_{i,m+1}=\texttt0$ is guaranteed. Yuki plans to place some rooks on the board. For a cell $(i,j)$, it is called safe if and only if there exists at least one rook in row $i$ or column $j$, and there is no rook on cell $(i,j)$. Yuki has the following requirements for a rook placement: - All rooks are placed on black cells. - No two rooks are in the same row or the same column. - A pawn starts from row $0$ of the board and **cannot** reach row $n+1$ while passing only through safe cells. The pawn moves as follows: suppose the pawn is currently at $(i,j)$. Then it can move to any one of $(i+1,j)$, $(i,j-1)$, $(i,j+1)$, as long as the destination is inside the board. You need to help Yuki compute the number of placements that satisfy the conditions. Since the answer may be large, output the result modulo $10^9+7$.

**This problem contains multiple test cases.** The first line of input contains two positive integers $t,c$, representing the number of test cases and the test point ID. The sample satisfies $c=0$. For each test case: - The first line contains two positive integers $n,m$. - The next $n$ lines describe the board. Line $i$ contains a $\texttt 01$ string of length $m$, $s_{i,1},\dots,s_{i,m}$.

For each test case, output one line containing one integer, the answer.

### Explanation of Sample 1 This sample has $3$ test cases. For test case $1$, the $3$ valid placements are: - Place no rooks. - Place a rook at $(1,1)$. - Place a rook at $(1,2)$. For test case $2$, the $3$ valid placements are: - Place no rooks. - Place a rook at $(1,2)$. - Place a rook at $(2,2)$. For test case $3$, the $4$ valid placements are: - Place no rooks. - Place a rook at $(1,1)$. - Place a rook at $(3,3)$. - Place rooks at $(1,1),(3,3)$. ### Sample 2 See $\boldsymbol{zu2.in}$ and $\boldsymbol{zu2.ans}$ in the additional files. This sample has $3$ test cases. In it, test case $1$ satisfies $n,m \le 4$, test case $2$ satisfies $n \le 100$, $m \le 4$, and test case $3$ satisfies $n \le 200$, $m \le 8$. ### Sample 3 See $\boldsymbol{zu3.in}$ and $\boldsymbol{zu3.ans}$ in the additional files. This sample has $3$ test cases. All testdata in this sample satisfies $s_{i,j}=1$. In it, test case $1$ satisfies $n,m \le 80$, test case $2$ satisfies $n,m \le 300$, and test case $3$ satisfies $n,m \le 1500$. ### Sample 4 See $\boldsymbol{zu4.in}$ and $\boldsymbol{zu4.ans}$ in the additional files. This sample has $3$ test cases. In it, test case $1$ satisfies $n,m \le 80$, test case $2$ satisfies $n,m \le 500$, and test case $3$ satisfies $n,m \le 3000$. ### Constraints For all testdata, it is guaranteed that: - $1 \le t \le 3$. - $1 \le n,m \le 3000$. - $s_{i,j} \in \{\texttt0,\texttt1\}$. **For test points where $\boldsymbol c$ is odd, it is guaranteed that $\boldsymbol{n=m}$.** ::cute-table{tuack} | Test Point ID | $n \le$ | $m \le$ | Special Property | | :-----------: | :-----: | :-----: | :--------------: | | $1 \sim 4$ | $100$ | $4$ | No | | $5 \sim 8$ | $200$ | $8$ | No | | $9,10$ | $1$ | $1500$ | No | | $11,12$ | $1500$ | $1$ | No | | $13,14$ | $80$ | $80$ | Yes | | $15,16$ | $300$ | $300$ | Yes | | $17,18$ | $1500$ | $1500$ | Yes | | $19 \sim 21$ | $80$ | $80$ | No | | $22,23$ | $500$ | $500$ | No | | $24,25$ | $3000$ | $3000$ | No | Special Property: for all $i \in [1,n],j \in [1,m]$, it is guaranteed that $s_{i,j}=\texttt1$. Translated by ChatGPT 5