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 2ドルn$ 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円$.

제한

힌트