23125번 - Joke 다국어

Consider two permutations of integers from $1$ to $n$: $p$ and $q$. Let us call a binary string $s$ of length $n$ satisfying if there exists a matrix $a$ with dimensions $2 \times n$ such that:

• Every integer from $1$ to $2n$ appears exactly once in the matrix.
• The elements in the first row are ordered correspondingly to permutation $p$. More formally, $a_{1, i} < a_{1, j} \iff p_i < p_j$ for $1 \le i < j \le n$.
• The elements in the second row are ordered correspondingly to permutation $q$. More formally, $a_{2, i} < a_{2, j} \iff q_i < q_j$ for $1 \le i < j \le n$.
• For every $i$ from $1$ to $n$, we have $a_{1, i} < a_{2, i} \iff s_i = $0.

For two permutations $p$ and $q$ of size $n$, let us define $f(p, q)$ as the number of satisfying strings $s$ for them.

You are given all elements of $p$, and several elements of $q$, but forgot others. Find the sum of $f(p, q)$ over all permutations $q$ with the given known elements, modulo $998\,244\,353$.

The first line of the input contains a single integer $n$ ($1 \le n \le 100$).

The second line of the input contains $n$ integers $p_1, p_2, \ldots, p_n$ ($1 \le p_i \le n$, all $p_i$ are distinct), a permutation of numbers from $1$ to $n$.

The second line of the input contains $n$ integers $q_1, q_2, \ldots, q_n$ ($0 \le q_i \le n$, $q_i \neq q_j$ when $q_i \neq 0$ and $q_j \neq 0$). If $q_i \neq 0$, the respective element is given. If $q_i = 0$, its value is forgotten. All given elements are distinct.

Output the sum of $f(p, q)$ over all valid permutations $q$ modulo $998\,244\,353$.