Problem Description

Three men A, B, and C decided to eat sushi together. Initially, there are $N$ types of sushi, each with one piece. The sushi are numbered from $1$ to $N$, where $N$ is a multiple of $3$.

Each of the three men has a preference ranking for the sushi. A's ranking is represented by a permutation of $1$ to $N$, denoted as $(a_1, ..., a_N)$. For each $i$ ($1 \leq i \leq N$), the $i$-th favorite sushi for A is sushi $a_i$. Similarly, B's and C's rankings are represented by permutations $(b_1, ..., b_N)$ and $(c_1, ..., c_N)$, respectively.

Until all the sushi are gone or a fight breaks out (described later), the three men repeat the following actions:

• A, B, and C each find their most preferred remaining sushi. Let these be sushi $x$, $y$, and $z$, respectively. If $x$, $y$, and $z$ are all different, then A, B, and C eat sushi $x$, $y$, and $z$, respectively. Otherwise, the three men start a fight.

Given A's and B's rankings $(a_1, ..., a_N)$ and $(b_1, ..., b_N)$, how many permutations of C's ranking $(c_1, ..., c_N)$ allow the three men to eat all the sushi without starting a fight? Find the answer modulo $10^9+7$.

Input Format

The input is given from the standard input in the following format:

$N$ $a_1$ $...$ $a_N$ $b_1$ $...$ $b_N$

Output Format

Output the number of permutations of C's ranking $(c_1, ..., c_N)$ that allow the three men to eat all the sushi without starting a fight, modulo $10^9+7$.

Sample Input and Output

Sample Input #1

3
1 2 3
2 3 1

Sample Output #1

2

Sample Input #2

3
1 2 3
1 2 3

Sample Output #2

0

Sample Input #3

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

Sample Output #3

80

Sample Input #4

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

Sample Output #4

160

Sample Input #5

9
4 5 6 7 8 9 1 2 3
7 8 9 1 2 3 4 5 6

Sample Output #5

33600

Notes/Hints

Constraints

• $3 \leq N \leq 399$
• $N$ is a multiple of $3$.
• $(a_1, ..., a_N)$ and $(b_1, ..., b_N)$ are permutations of $1$ to $N$.

Sample Explanation 1

There are $2$ ways: $(c_1, c_2, c_3) = (3, 1, 2), (3, 2, 1)$. In both cases, A, B, and C eat sushi $1$, $2$, and $3$ respectively, and all the sushi are gone.

Sample Explanation 2

No matter what permutation $(c_1, c_2, c_3)$ is, A and B both want to eat sushi $1$, so a fight breaks out.

Sample Explanation 3

For example, if $(c_1, c_2, c_3, c_4, c_5, c_6) = (5, 1, 2, 6, 3, 4)$, first A, B, and C eat sushi $1$, $2$, and $5$ respectively, then A, B, and C eat sushi $3$, $4$, and $6$ respectively, and all the sushi are gone.

见题面 Input 部分

见题面 Output 部分