Путь по сетке называется жадным, если он начинается в верхнем левом углу и движется только вправо или вниз, всегда перемещаясь к соседу с большим значением (или к любому соседу, если их значения равны).
Значение пути — это сумма значений ячеек, которые он посещает, включая начальную и конечную.
Дана сетка $$$2 \times n$$$, частично заполненная целыми числами от $$$1$$$ до $$$k$$$. Подсчитайте количество способов заполнить пустые ячейки так, чтобы в каждой подсетке$$$^{\text{∗}}$$$ существовал жадный путь, который достигает максимального значения среди всех путей, идущих только вниз и вправо. Поскольку ответ может быть очень большим, выведите его по модулю $$$998\,244\,353$$$.
$$$^{\text{∗}}$$$ Подсеткой сетки $$$a_{i,j}$$$ размера $$$2 \times n$$$ называется сетка, образованная из всех ячеек $$$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}. $$$$$$
Во втором наборе входных данных все способы заполнить сетку удовлетворяют условиям.
