F. Paths on a Grid
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are given a grid $$$a$$$ of size $$$n \times m$$$. The rows are numbered from $$$1$$$ to $$$n$$$ from top to bottom, and the columns are numbered from $$$1$$$ to $$$m$$$ from left to right. Each cell of the grid is either blocked or free. Cells $$$(1, 1)$$$ and $$$(n, m)$$$ are free.

A set $$$S$$$ of cells of $$$a$$$, which may include blocked cells, is called good if the following conditions hold:

  • $$$S$$$ is non-empty;
  • for every cell $$$(i, j)$$$ belonging to $$$S$$$, every path from $$$(1, 1)$$$ to $$$(n, m)$$$ that passes only through free cells, moves one cell down or one cell right at each step, and passes through $$$(i, j)$$$ also passes through all other cells of $$$S$$$.

Count the number of good sets of cells of $$$a$$$ modulo $$$998\,244\,353$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \cdot m \le 10^6$$$).

The $$$i$$$-th of the following $$$n$$$ lines contains a string $$$a_{i, 1} a_{i, 2} \ldots a_{i, m}$$$ ($$$a_{i, j} \in \{0, 1\}$$$) — the $$$i$$$-th row of the grid. If $$$a_{i, j} = 1$$$, then cell $$$(i, j)$$$ is free; otherwise, it is blocked. It is guaranteed that $$$a_{1, 1} = a_{n, m} = 1$$$.

It is guaranteed that the sum of $$$n \cdot m$$$ over all test cases does not exceed $$$10^6$$$.

Output

For each test case, output a single integer — the answer to the problem modulo $$$998\,244\,353$$$.

Example
Input
6
1 1
1
2 2
11
11
2 2
10
01
2 2
11
01
4 4
1011
1101
0111
1111
1 32
10010110010001010110011111010011
Output
1
5
15
8
162
301989883
Note

In the first example, the only non-empty set of cells is $$$\{(1, 1)\}$$$, and it is good. Therefore, the answer is $$$1$$$.

In the third example, there is no path from $$$(1, 1)$$$ to $$$(2, 2)$$$ that passes only through free cells. Therefore, every non-empty set of cells is good, so the answer is $$$2^4 - 1 = 15$$$.

In the fifth example, the set $$$\{(2, 2), (3, 2)\}$$$ is good because every path from $$$(1, 1)$$$ to $$$(4, 4)$$$ that passes only through free cells and passes through either of these cells also passes through the other. On the other hand, the set $$$\{(3, 3), (4, 3)\}$$$ is not good: the path $$$(1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (3, 2) \rightarrow (3, 3) \rightarrow (3, 4) \rightarrow (4, 4)$$$ passes through $$$(3, 3)$$$ but does not pass through $$$(4, 3)$$$. It can be shown that the total number of good sets is $$$162$$$.