Problem Description

Unputdownable has a permutation $a$ of length $n$.

While practicing monotonic stacks, he used a program to compute, for each $i$, the largest $l_i$ such that $a_{l_i} < a_i$ and $l_i < i$, and the smallest $r_i$ such that $a_{r_i} < a_i$ and $r_i > i$.

In particular, if such an $l_i$ does not exist, it is defined as $0$, and if such an $r_i$ does not exist, it is defined as $n+1$.

One day, Unputdownable forgot the permutation $a$, and only the arrays $l$ and $r$ after being rearranged separately were left. Can you help him recover the original permutation $a$?

Later, since he found that $a$ cannot be recovered, you only need to tell him how many possible original permutations $a$ there are.

Output the answer modulo $998244353$. The testdata guarantees that at least one solution exists.

Input Format

The first line contains an integer $n$.

The second line contains $n$ integers, representing the rearranged $l$.

The third line contains $n$ integers, representing the rearranged $r$.

Output Format

Output one line containing one integer, the number of possible permutations modulo $998244353$.

5
3 1 0 0 4
6 3 6 3 6

6

Hint

Sample Explanation 1

One possible permutation is $\{2,5,1,3,4\}$. The $l$ array is $\{0,1,0,3,4\}$, and the $r$ array is $\{3,3,6,6,6\}$.

This problem uses bundled tests.

• Subtask 1 (5 pts): $n \leq 8$.
• Subtask 2 (15 pts): $r_i \geq n$.
• Subtask 3 (15 pts): $n \leq 2000$, and it is guaranteed that there exists a permutation $a$ such that the $l, r$ computed from $a$ are exactly the given ones.
• Subtask 4 (25 pts): $n \leq 10^6$, and it is guaranteed that there exists a permutation $a$ such that the $l, r$ computed from $a$ are exactly the given ones.
• Subtask 5 (40 pts): No special constraints.

For $100\%$ of the testdata, $1 \leq n \leq 10^6$, $0 \leq l_i, r_i \leq n+1$. The testdata guarantees that at least one solution exists.

Translated by ChatGPT 5