Problem Statement

You are given an integer $N$ and integer sequences $P=(P_1,P_2,\ldots, P_N)$ and $Q=(Q_1,Q_2,\ldots,Q_N)$, each of which is a permutation of $(1,2,\ldots,N)$.

Find the number of integer sequences that are a permutation of $(1,2,\ldots,N)$ and are lexicographically greater than $P$ and lexicographically less than $Q$.

What is lexicographic order for integer sequences? For integer sequences $S = (S_1,S_2,\ldots,S_{|S|})$ and $T = (T_1,T_2,\ldots,T_{|T|})$, we say that $S$ is lexicographically smaller than $T$ if $1.$ or $2.$ below holds. Here, $|S|, |T|$ denote the lengths of $S, T$, respectively. $|S| \lt |T|$ and $(S_1,S_2,\ldots,S_{|S|}) = (T_1,T_2,\ldots,T_{|S|})$. There exists an integer $1 \leq i \leq \min\lbrace |S|, |T| \rbrace$ such that both of the following two conditions hold. $(S_1,S_2,\ldots,S_{i-1}) = (T_1,T_2,\ldots,T_{i-1})$ $S_i$ is (numerically) smaller than $T_i$.

Constraints

• $1\le N\le 10$
• $P$ and $Q$ are integer sequences that are permutations of $(1,2,\ldots,N)$.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

N
P_1 P_2 \ldots P_N
Q_1 Q_2 \ldots Q_N

Output

Output the answer.