Problem Background

It is recommended to rate this problem as Brown.

Problem Description

Yuki has a chessboard with $n+2$ rows and $m+2$ columns, where rows are indexed from $0$ to $n+1$ and columns are indexed from $0$ to $m+1$.

The cell at row $i$ and column $j$ is denoted by $(i,j)$. Each cell is either white or black, represented by $s_{i,j}$, where $s_{i,j} = \texttt0$ indicates white and $s_{i,j} = \texttt1$ indicates black. It is guaranteed that the outermost border of the chessboard consists of white cells, i.e., $s_{0,i}=s_{n+1,i}=s_{i,0}=s_{i,m+1}=\texttt0$.

Yuki intends to place several rooks on the chessboard. A cell $(i,j)$ is called safe if and only if there is 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 the placement of the rooks:

• All rooks must be placed on black cells;
• No two rooks can be in the same row or the same column;
• A pawn starting from row $0$ cannot reach row $n+1$ by moving only through safe cells.

The pawn moves as follows: if the current position of the pawn is $(i,j)$, it can move to any of $(i+1,j), (i,j-1), (i,j+1)$, provided the destination is within the chessboard.

Yuki needs your help to find the number of valid rook placement schemes. Since the answer may be large, you only need to output the answer modulo $10^9+7$.

Input

This problem contains multiple test cases.

The first line contains two positive integers $t$ and $c$, representing the number of test cases and the test point ID, respectively. The sample satisfies $c=0$.

For each test case:

• The first line contains two positive integers $n$ and $m$.
• The next $n$ lines each contain a $\texttt{01}$ string of length $m$, representing $s_{i,1}, \dots, s_{i,m}$.

Output

For each test case, output a single integer representing the answer.

Examples

Input 1

3 0
2 2
11
00
2 2
01
01
3 3
100
000
001

Output 1

3
3
4

Note 1

There are $3$ test cases in this sample.

For the first test case, the $3$ valid schemes are: - No rooks placed; - A rook at $(1,1)$; - A rook at $(1,2)$.

For the second test case, the $3$ valid schemes are: - No rooks placed; - A rook at $(1,2)$; - A rook at $(2,2)$.

For the third test case, the $4$ valid schemes are: - No rooks placed; - A rook at $(1,1)$; - A rook at $(3,3)$; - Rooks at $(1,1)$ and $(3,3)$.

Input 2

See $\boldsymbol{zu2.in}$ and $\boldsymbol{zu2.ans}$ in the additional files.

This sample contains $3$ test cases. The first test case satisfies $n,m \le 4$, the second satisfies $n \le 100, m \le 4$, and the third satisfies $n \le 200, m \le 8$.

Input 3

See $\boldsymbol{zu3.in}$ and $\boldsymbol{zu3.ans}$ in the additional files.

This sample contains $3$ test cases. All test cases satisfy $s_{i,j} = 1$. The first test case satisfies $n,m \le 80$, the second satisfies $n,m \le 300$, and the third satisfies $n,m \le 1500$.

Input 4

See $\boldsymbol{zu4.in}$ and $\boldsymbol{zu4.ans}$ in the additional files.

This sample contains $3$ test cases. The first test case satisfies $n,m \le 80$, the second satisfies $n,m \le 500$, and the third satisfies $n,m \le 3000$.

Constraints

For all test cases, 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}$.

Special Property: For all $i \in [1,n], j \in [1,m]$, it is guaranteed that $s_{i,j}=\texttt1$.