J. Joke
time limit per test
2 seconds
memory limit per test
512 mebibytes
input
standard input
output
standard output

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} \lt a_{1, j} \iff p_i \lt p_j$$$ for $$$1 \le i \lt j \le n$$$.
  • The elements in the second row are ordered correspondingly to permutation $$$q$$$. More formally, $$$a_{2, i} \lt a_{2, j} \iff q_i \lt q_j$$$ for $$$1 \le i \lt j \le n$$$.
  • For every $$$i$$$ from $$$1$$$ to $$$n$$$, we have $$$a_{1, i} \lt a_{2, i} \iff s_i = \texttt{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$$$.

Input

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

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

Examples
Input
2
1 2
2 1
Output
3
Input
4
4 3 2 1
4 3 2 1
Output
16
Input
5
1 2 3 4 5
0 0 0 0 0
Output
1546
Input
6
1 6 2 5 3 4
0 1 0 2 0 3
Output
52