Little C is a computer science student. This semester, he is taking Professor H's Introduction to Computing course.

There is no midterm exam for this course; instead, there is a large midterm project. The project requirements are as follows:

Professor H provides a permutation $q_1, q_2, \dots, q_n$ of $1$ to $n$, and an additional array $h_1, h_2, \dots, h_n$ of length $n$ containing integers.

Professor H defines the "beauty" $val$ of a permutation $p$ of $1$ to $n$ as $\displaystyle \sum_{i=1}^n \sum_{j=i+1}^n [p_i \geq p_j]+[(p_i + h_i) \geq q_j]$.

Little C needs to calculate how many such permutations exist whose beauty is an even number. Since the answer can be very large, you only need to submit the answer modulo $998\,244\,353$.

Little C feels that the professor is bullying a novice who has only been studying computer science for 3 months, so he has come to you, who are training here, to help him solve this problem.

Input

The first line contains a positive integer $n$.

The second line contains $n$ space-separated positive integers, where the $i$-th number is $q_i$.

The third line contains $n$ space-separated integers, where the $i$-th number is $h_i$.

Output

A single integer representing the number of permutations $P$ with an even beauty, modulo $998\,244\,353$.

Examples

Input 1

3
2 1 3
0 0 0

Output 1

3

Note 1

The beauty of 1 2 3 is $1$.

The beauty of 1 3 2 is $3$.

The beauty of 2 1 3 is $2$.

The beauty of 2 3 1 is $4$.

The beauty of 3 1 2 is $4$.

The beauty of 3 2 1 is $5$.

Subtasks

• Subtask 1 [20 points]: $n \leq 20$.
• Subtask 2 [30 points]: $h_i = 0$.
• Subtask 3 [50 points]: No additional restrictions.

For all test data, it is guaranteed that $1 \leq n \leq 300$, $-n \leq h_i \leq n$, and $q_i$ is a permutation of $1 \sim n$.