{"raw_statement":[{"iden":"problem statement","content":"You are going to create $N$ sequences of length $3$, satisfying the following conditions.\n\n*   For each of $k = 1,2,3$, the following holds:\n    *   Among the $k$\\-th elements of the sequences, each integer from $1$ through $N$ appears exactly once.\n\nFor this sequence of sequences, define sequences $a=(a_1,a_2,\\ldots,a_N)$ and $b=(b_1,b_2,\\ldots,b_N)$ as follows.\n\n*   Let $s_i$ be the $i$\\-th sequence, and let $t_i$ be the reverse of the $i$\\-th sequence. When all of these are sorted in lexicographical order, $s_i$ comes $a_i$\\-th, and $t_i$ comes $b_i$\\-th.\n*   Here, if there are identical sequences among the $2N$ sequences, $a$ and $b$ are not defined.\n\nTherefore, if $a$ and $b$ are defined, each integer from $1$ through $2N$ appears exactly once in the concatenation of $a$ and $b$.\nYou are given sequences $A$ and $B$ of length $N$, where each element of $A$ is an integer between $1$ and $2N$, and each element of $B$ is either an integer between $1$ and $2N$ or $-1$. Also, in the concatenation of $A$ and $B$, each integer other than $-1$ appears at most once.\nHow many pairs of sequences $a,b$ are there such that $a$ and $b$ are defined and the following holds for each integer $i$ from $1$ through $N$?\n\n*   $a_i = A_i$.\n*   $b_i = B_i$ if $B_i \\neq -1$.\n\nFind the count modulo $998244353$."},{"iden":"constraints","content":"*   $2 \\leq N \\leq 3000$\n*   $1 \\leq A_i \\leq 2N$\n*   $1 \\leq B_i \\leq 2N$ or $B_i = -1$.\n*   In the concatenation of $A$ and $B$, each integer other than $-1$ appears at most once. That is,\n    *   $A_i \\neq A_j$ if $i \\neq j$.\n    *   $B_i \\neq B_j$ if $i \\neq j$ and $B_i,B_j \\neq -1$.\n    *   $A_i \\neq B_j$.\n*   All input values are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$\n$A_1$ $A_2$ $\\ldots$ $A_N$\n$B_1$ $B_2$ $\\ldots$ $B_N$"},{"iden":"sample input 1","content":"3\n2 3 6\n-1 1 -1"},{"iden":"sample output 1","content":"1\n\nFor example, consider creating the following three sequences:\n\n1.  $(1,2,3)$\n2.  $(2,1,1)$\n3.  $(3,3,2)$\n\nIn this case, when sorting $s_i$ and $t_i$ lexicographically, we have:\n\n> $t_2 = (1,1,2) < s_1 = (1,2,3) < s_2 = (2,1,1) < t_3 = (2,3,3) < t_1 = (3,2,1) < s_3 = (3,3,2)$\n\nThus, $(a_1,a_2,a_3,b_1,b_2,b_3) = (2,3,6,5,1,4)$. Here, $a$ matches the given $A$, and the second element of $b$ also matches that of $B$, so this is one pair of sequences $a,b$ satisfying the conditions.\nOn the other hand, if we create the following three sequences, $s_1$ and $t_1$ become identical, so $a$ and $b$ are not defined.\n\n1.  $(1,2,1)$\n2.  $(2,1,3)$\n3.  $(3,3,2)$\n\nIn fact, $a=(2,3,6), b=(5,1,4)$ is the only pair of sequences satisfying the conditions."},{"iden":"sample input 2","content":"15\n5 16 1 12 30 20 4 13 9 8 24 21 26 28 17\n-1 -1 6 -1 -1 -1 -1 -1 -1 -1 -1 29 -1 -1 -1"},{"iden":"sample output 2","content":"758094847\n\nPrint the count modulo $998244353$."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}