E. 贪婪网格计数
时间限制：4 秒
内存限制：256 兆字节

在一个网格中，如果一条路径从左上角单元格出发，且只能向右或向下移动，并且总是移动到数值更大的相邻单元格（若相等则可任选其一），则称其为贪婪路径。
路径的值定义为路径所经过单元格（包括起点和终点）的数值之和。

给定一个部分填充的 $2 \times n$ 网格，网格中的整数取值范围为 $1$ 到 $k$。计算填充所有空单元格的方式数，使得在每一个子网格*中，都存在一条贪婪路径，该路径能达到该子网格内所有向下/向右路径中的最大值。答案可能很大，请对 $998244353$ 取模。

• 一个 $2 \times n$ 网格 $a_{i,j}$ 的子网格是指由所有满足 $1 \le lx \le x \le rx \le 2$ 且 $1 \le ly \le y \le ry \le n$ 的单元格 $a_{x,y}$ 构成的网格。

---

输入
每个测试包含多个测试用例。第一行包含测试用例数 $t$（$1 \le t \le 500$）。
每个测试用例的描述如下：
第一行包含两个整数 $n$ 和 $k$（$1 \le n, k \le 500$）—— 网格的列数和整数的取值范围。
接下来两行，第 $i$ 行包含 $n$ 个整数 $a_{i,1}, a_{i,2}, \dots, a_{i,n}$（$-1 \le a_{i,j} \le k$，$a_{i,j} \neq 0$）—— 网格第 $i$ 行的值，其中 $-1$ 表示空单元格。

保证所有测试用例的 $n$ 之和不超过 $500$。

---

输出
对于每个测试用例，输出一个整数 —— 满足上述条件的填充方式数，对 $998244353$ 取模。

---

样例
输入

3
4 3
2 1 -1 2
2 -1 1 3
5 4
1 3 -1 4 2
-1 3 4 2 -1
10 10
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1

输出

6
64
123782927

---

说明
在第一个测试用例中，满足条件的网格为：

$$\begin{bmatrix} 2 & 1 & 1 & 2 \\ 2 & 1 & 1 & 3 \end{bmatrix},\quad \begin{bmatrix} 2 & 1 & 2 & 2 \\ 2 & 1 & 1 & 3 \end{bmatrix},\quad \begin{bmatrix} 2 & 1 & 3 & 2 \\ 2 & 1 & 1 & 3 \end{bmatrix},\quad \begin{bmatrix} 2 & 1 & 2 & 2 \\ 2 & 1 & 2 & 3 \end{bmatrix},\quad \begin{bmatrix} 2 & 1 & 3 & 2 \\ 2 & 1 & 2 & 3 \end{bmatrix},\quad \begin{bmatrix} 2 & 1 & 3 & 2 \\ 2 & 1 & 3 & 3 \end{bmatrix}. $$

在第二个测试用例中，所有填充方式均满足条件。