网格中的路径称为 贪婪 如果它从左上角单元格开始并且仅向右或向下移动,则始终移动到具有较大值的邻居(或者如果值相等)。
的 值 路径的 是其访问的单元格值的总和,包括起点和终点。
给定一个部分填充的 $$$2 \times n$$$ 介于 $$$1$$$ 和 $$$k$$$ 之间的整数网格,计算填充空单元格的方法数量,使得 每个子网格中的 在每个子网格中$$$^{\text{*}}$$$,存在一条贪婪路径,可以在所有向下/向右路径中获得最大值。由于答案可能很大,请以 $$$998\,244\,353$$$ 为模进行计算。
$$$^{\text{*}}$$$ $$$2 \times n$$$ 网格的子网格 $$$a_{i,j}$$$ 是由所有单元 $$$a_{x,y}$$$ 组成的网格,使得 $$$l_x \leq x \leq r_x$$$, $$$l_y \leq y \leq r_y$$$对于一些$$$1 \leq l_x \leq r_x \leq 2$$$,$$$1 \leq l_y \leq r_y \leq n$$$。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$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$$$ 为模。
示例
输入复制
34 32 1 -1 22 -1 1 35 41 3 -1 4 2-1 3 4 2 -110 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},\: \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}.$$
在第二个测试用例中,所有填充网格的方式都满足条件。