CF2247F.Paths on a Grid

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$.

给你一个大小为 $n \times m$ 的网格 $a$。行从上到下编号为 $1$ 到 $n$，列从左到右编号为 $1$ 到 $m$。网格中的每个单元格要么被阻塞，要么是空闲的。单元格 $(1, 1)$ 和 $(n, m)$ 均为空闲。

一个可能包含阻塞单元格的单元格集合 $S$ 被称为好集合，当且仅当满足以下条件：

• $S$ 非空；
• 对于每个属于 $S$ 的单元格 $(i, j)$，任意一条从 $(1, 1)$ 到 $(n, m)$ 的路径（该路径仅经过空闲单元格，每一步只能向下或向右移动一格），只要经过 $(i, j)$，则必然也经过 $S$ 中所有其他单元格。

求网格 $a$ 中好集合的个数，对 $998\,244\,353$ 取模。

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$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \le n \cdot m \le 10^6$）。

接下来的 $n$ 行中，第 $i$ 行包含一个字符串 $a_{i, 1} a_{i, 2} \ldots a_{i, m}$（其中 $a_{i, j} \in \{0, 1\}$），表示网格的第 $i$ 行。若 $a_{i, j} = 1$，则单元格 $(i, j)$ 是空闲的；否则该单元格被阻塞。保证 $a_{1, 1} = a_{n, m} = 1$。

保证所有测试用例中 $n \cdot m$ 的总和不超过 $10^6$。

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

对于每个测试用例，输出一个整数——问题答案对 $998\,244\,353$ 取模的结果。

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$.

在第一个例子中，唯一的非空单元格集合是 $\{(1, 1)\}$，且它是“好”的。因此答案为 $1$。

在第三个例子中，不存在一条从 $(1, 1)$ 到 $(2, 2)$ 的、仅经过空闲单元格的路径。因此，每个非空单元格集合都是“好”的，故答案为 $2^4 - 1 = 15$。

在第五个例子中，集合 $\{(2, 2), (3, 2)\}$ 是“好”的，因为每条从 $(1, 1)$ 到 $(4, 4)$ 的、仅经过空闲单元格且经过其中任一单元格的路径，也必然经过另一个单元格。另一方面，集合 $\{(3, 3), (4, 3)\}$ 不是“好”的：路径 $(1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (3, 2) \rightarrow (3, 3) \rightarrow (3, 4) \rightarrow (4, 4)$ 经过了 $(3, 3)$，但未经过 $(4, 3)$。可以证明，“好”集合的总数为 $162$。