For two permutations $p$ and $q$, a binary string $s$ is called "xiaochou" if and only if there exists a $2 \times n$ matrix $a$ such that:

1. Every element from $1$ to $2n$ appears in the matrix exactly once.
2. $a_{1,i} < a_{1,j}$ if and only if $p_i < p_j$.
3. $a_{2,i} < a_{2,j}$ if and only if $q_i < q_j$.
4. $a_{1,i} < a_{2,i}$ if and only if $s_i = 0$.

Let $f(p, q)$ be the number of binary strings $s$ that are "xiaochou" for these two permutations.

Given a partial permutation $q$ and a full permutation $p$, calculate the sum of $f(p, q)$ over all possible ways to complete $q$.

Input

The first line contains an integer $n$, the length of the permutations.

The second line contains $n$ integers representing the permutation $p$.

The third line contains $n$ integers representing the partial permutation $q$, where $q_i = 0$ indicates that the value at this position is unknown.

Output

Output the sum of $f(p, q)$ modulo $998244353$.

Examples

Input 1

2
1 2
2 1

Output 1

3

Note 1

00 corresponds to:

1 2
4 3

11 corresponds to:

3 4
2 1

01 corresponds to:

1 4
3 2

Input 2

4
4 3 2 1
4 3 2 1

Output 2

16

Input 3

5
1 2 3 4 5
0 0 0 0 0

Output 3

1546

Input 4

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

Output 4

52

Constraints

For $100\%$ of the data, $1 \leq n \leq 100$, $1 \leq p_i \leq n$, $0 \leq q_i \leq n$. For $i \neq j$, $p_i \neq p_j$, and if $q_i, q_j \neq 0$, then $q_i \neq q_j$.