시간 제한메모리 제한제출정답맞은 사람정답 비율
2 초 512 MB95360.000%

문제

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$.

예제 입력 1

2
1 2
2 1

예제 출력 1

3

예제 입력 2

4
4 3 2 1
4 3 2 1

예제 출력 2

16

예제 입력 3

5
1 2 3 4 5
0 0 0 0 0

예제 출력 3

1546

예제 입력 4

6
1 6 2 5 3 4
0 1 0 2 0 3

예제 출력 4

52