CF2122E Greedy Grid Counting

A path in a grid is called greedy if it starts at the top-left cell and moves only to the right or downward, always moving to its neighbor with the greater value (or either if the values are equal). The value of a path is the sum of the values of the cells it visits, including the start and end. Given a partially filled $ 2 \times n $ grid of integers between $ 1 $ and $ k $ , count the number of ways to fill the empty cells such that in every subgrid $ ^{\text{∗}} $ , there exists a greedy path that achieves the maximum value out of all down/right paths. Since the answer may be large, calculate it modulo $ 998\,244\,353 $ . $ ^{\text{∗}} $ A subgrid of a $ 2 \times n $ grid $ a_{i,j} $ is a grid formed from all cells $ a_{x,y} $ such that $ l_x \leq x \leq r_x $ , $ l_y \leq y \leq r_y $ for some $ 1 \leq l_x \leq r_x \leq 2 $ , $ 1 \leq l_y \leq r_y \leq n $ .

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 500 $ ). The description of the test cases follows. The first line of each test case contains two integers $ n $ and $ k $ ( $ 1 \leq n, k \leq 500 $ ) — the number of columns and the range of integers in the grid, respectively. Then two lines follow, the $ i $ -th line containing $ n $ integers $ a_{i,1}, a_{i,2}, \ldots, a_{i,n} $ ( $ -1 \leq a_{i,j} \leq k $ , $ a_{i,j} \neq 0 $ ) — the values of cells in the $ i $ -th row of the grid, where $ -1 $ represents an empty cell. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 500 $ .

For each test case, output a single integer — the number of ways to fill the grid that satisfy the above conditions, modulo $ 998\,244\,353 $ .

In the first test case, the grids that satisfy the conditions are: $$ \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}. $$ In the second test case, all ways to fill the grid satisfy the conditions.