AT_scpc2026_div1_g.오fill

Cenix wants to fill an $N \times M$ grid using the following six types of square tiles. There are plenty of each type of tile, and they can be rotated before placement. When placing tiles, every edge connected to a path must touch an edge connected to a path on a neighboring tile. However, not all paths need to be connected.

While filling the grid, Cenix realized that the task was too easy. Cenix now intends to fill the remaining cells using only tiles that connect one side and tiles that connect three sides.

A grid with some cells already filled with tiles is given as follows.

• The type of tile placed in the $i$-th row and $j$-th column of the grid is denoted by $A_{i,j}$.
  • If no tile is placed in that cell, $A_{i,j}$ is $-1$.
  • If a tile is placed in that cell, $A_{i,j}$ is the sum of $1$ (if the tile is connected to the top edge), $2$ (if connected to the bottom edge), $4$ (if connected to the left edge), and $8$ (if connected to the right edge).

Find the number of ways to fill the remaining cells using only these two types of tiles.

Cenix 想要用以下六种类型的方形单元格瓷砖铺满一个 $N \times M$ 的网格。每种瓷砖均有无限供应，且可在放置前任意旋转。放置瓷砖时，每条与路径相连的边必须与相邻瓷砖上一条同样与路径相连的边相接。但并非所有路径都必须相互连通。

在铺填过程中，Cenix 发现该任务过于简单。因此，Cenix 决定：仅使用仅连接一侧的瓷砖和连接三侧的瓷砖来填充剩余的空单元格。

给定一个部分已铺填瓷砖的网格，具体如下：

• 网格中第 $i$ 行、第 $j$ 列单元格所放置的瓷砖类型记为 $A_{i,j}$。
  • 若该单元格尚未放置瓷砖，则 $A_{i,j} = -1$；
  • 若该单元格已放置瓷砖，则 $A_{i,j}$ 定义为如下各项之和：若瓷砖与上边相连则加 $1$，与下边相连则加 $2$，与左边相连则加 $4$，与右边相连则加 $8$。

求仅用上述两种瓷砖（即仅连接一侧与连接三侧的瓷砖）填满所有剩余空单元格的方案总数。

The input is given from Standard Input in the following format:

$N$ $M$
$A_{1,1}$ $A_{1,2}$ $\dots$ $A_{1,M}$
$A_{2,1}$ $A_{2,2}$ $\dots$ $A_{2,M}$
$\vdots$
$A_{N,1}$ $A_{N,2}$ $\dots$ $A_{N,M}$

输入从标准输入中按以下格式给出：

$N$ $M$
$A_{1,1}$ $A_{1,2}$ $\dots$ $A_{1,M}$
$A_{2,1}$ $A_{2,2}$ $\dots$ $A_{2,M}$
$\vdots$
$A_{N,1}$ $A_{N,2}$ $\dots$ $A_{N,M}$

Output the number of ways to fill the grid, modulo $998\,244\,353$.

输出填充网格的方案数，对 $998\,244\,353$ 取模。

表示言語

/ /

Sample 1 Explanation:

Constraints

• $1 \le N, M \le 500\,000$
• $1 \le NM \le 500\,000$
• $-1 \le A_{i,j} \le 15$
• All input values are integers.

表示语言

/ /

样例 1 解释：

约束条件

• $1 \le N, M \le 500\,000$
• $1 \le NM \le 500\,000$
• $-1 \le A_{i,j} \le 15$
• 所有输入值均为整数。