CF2122E Greedy Grid Counting

网格中的路径若满足以下条件则称为贪心路径：从左上角单元格出发，仅能向右或向下移动，且每次必须移动到相邻数值更大的单元格（若相邻值相等则可任选其一）。 路径的数值等于其经过所有单元格（包括起点和终点）的数值之和。 给定一个部分填充的 $2 \times n$ 整数网格（数值范围 $1$ 至 $k$），计算填充空白单元格的方案数，使得**每个子网格**$^{\text{∗}}$中都存在一条贪心路径，其数值等于该子网格所有下/右路径中的最大值。由于答案可能很大，请对 $998\,244\,353$ 取模。 $^{\text{∗}}$ 对于 $2 \times n$ 网格 $a_{i,j}$，其子网格由满足 $1 \leq l_x \leq r_x \leq 2$ 和 $1 \leq l_y \leq r_y \leq n$ 的所有单元格 $a_{x,y}$（其中 $l_x \leq x \leq r_x$，$l_y \leq y \leq r_y$）构成。

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 500$）。接下来是每个测试用例的描述。 每个测试用例的第一行包含两个整数 $n$ 和 $k$（$1 \leq n, k \leq 500$）—— 分别表示网格的列数和网格中整数的取值范围。 随后是两行，第 $i$ 行包含 $n$ 个整数 $a_{i,1}, a_{i,2}, \ldots, a_{i,n}$（$-1 \leq a_{i,j} \leq k$，$a_{i,j} \neq 0$）—— 表示网格第 $i$ 行单元格的值，其中 $-1$ 表示空单元格。 保证所有测试用例的 $n$ 之和不超过 $500$。

对于每个测试用例，输出一个整数——满足上述条件的网格填充方案数，对 $998\,244\,353$ 取模。

在第一个测试用例中，满足条件的网格如下： $$ \begin{bmatrix} 2 & 1 & 1 & 2 \\ 2 & 1 & 1 & 3 \end{bmatrix},\: \begin{bmatrix} 2 & 1 & 1 & 2 \\ 2 & 2 & 1 & 3 \end{bmatrix},\: \begin{bmatrix} 2 & 1 & 1 & 2 \\ 2 & 3 & 1 & 3 \end{bmatrix},\: \begin{bmatrix} 2 & 1 & 2 & 2 \\ 2 & 2 & 1 & 3 \end{bmatrix},\: \begin{bmatrix} 2 & 1 & 2 & 2 \\ 2 & 3 & 1 & 3 \end{bmatrix},\: \begin{bmatrix} 2 & 1 & 3 & 2 \\ 2 & 3 & 1 & 3 \end{bmatrix}. $$ 在第二个测试用例中，所有填充网格的方式均满足条件。