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

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

For each test case, output a single integer — the answer to the problem modulo $ 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 $ .