F - Three Gluttons

Time Limit: 2 sec / Memory Limit: 512 MB

配点 : 1800

問題文

3 人の男性 A, B, C が一緒に寿司を食べることになりました。 最初、N 種類の寿司が 1 個ずつあります。 寿司には 1 から N まで番号が振られています。 ただし、N3 の倍数とします。

3 人はそれぞれ寿司に対して好き嫌いの順位付けを持っています。 A の順位付けは、1 から N までの順列 (a_1,\ ...,\ a_N) で表されます。 各 i (1 \leq i \leq N) について、A が i 番目に好きな寿司は寿司 a_i です。 同様に、B および C の順位付けは、1 から N までの順列 (b_1,\ ...,\ b_N) および (c_1,\ ...,\ c_N) で表されます。

寿司がすべて無くなるか、喧嘩が起こる (後述) まで、3 人は次の行動を繰り返します。

  • A, B, C はそれぞれ、残りの寿司のうち最も好きな寿司を見つける。 これらをそれぞれ寿司 x, y, z とする。 x, y, z がすべて相異なるならば、A, B, C はそれぞれ寿司 x, y, z を食べる。 そうでないならば、3 人は殴り合いの喧嘩を始める。

A および B の順位付け (a_1,\ ...,\ a_N) および (b_1,\ ...,\ b_N) が与えられます。 C の順位付け (c_1,\ ...,\ c_N) のうち、3 人が喧嘩を始めることなく寿司をすべて食べ切れるようなものは、何通りあるでしょうか? 10^9+7 で割った余りを求めてください。

制約

  • 3 \leq N \leq 399
  • N3 の倍数である。
  • (a_1,\ ...,\ a_N) および (b_1,\ ...,\ b_N)1 から N までの順列である。

入力

入力は以下の形式で標準入力から与えられる。

N
a_1 ... a_N
b_1 ... b_N

出力

C の順位付け (c_1,\ ...,\ c_N) のうち、3 人が喧嘩を始めることなく寿司をすべて食べ切れるようなものは、何通りあるか? 10^9+7 で割った余りを出力せよ。


入力例 1

3
1 2 3
2 3 1

出力例 1

2

(c_1,\ c_2,\ c_3) = (3,\ 1,\ 2),\ (3,\ 2,\ 1)2 通りです。 どちらの場合も、A, B, C はそれぞれ寿司 1, 2, 3 を食べ、寿司がすべて無くなります。


入力例 2

3
1 2 3
1 2 3

出力例 2

0

(c_1,\ c_2,\ c_3) がどのような順列であっても、A と B はともに寿司 1 を食べようとするので、喧嘩が起こります。


入力例 3

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

出力例 3

80

例えば (c_1,\ c_2,\ c_3,\ c_4,\ c_5,\ c_6) = (5,\ 1,\ 2,\ 6,\ 3,\ 4) の場合、まず A, B, C はそれぞれ寿司 1, 2, 5 を食べ、次に A, B, C はそれぞれ寿司 3, 4, 6 を食べ、寿司がすべて無くなります。


入力例 4

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

出力例 4

160

入力例 5

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

出力例 5

33600

Score : 1800 points

Problem Statement

Three men, A, B and C, are eating sushi together. Initially, there are N pieces of sushi, numbered 1 through N. Here, N is a multiple of 3.

Each of the three has likes and dislikes in sushi. A's preference is represented by (a_1,\ ...,\ a_N), a permutation of integers from 1 to N. For each i (1 \leq i \leq N), A's i-th favorite sushi is Sushi a_i. Similarly, B's and C's preferences are represented by (b_1,\ ...,\ b_N) and (c_1,\ ...,\ c_N), permutations of integers from 1 to N.

The three repeats the following action until all pieces of sushi are consumed or a fight brakes out (described later):

  • Each of the three A, B and C finds his most favorite piece of sushi among the remaining pieces. Let these pieces be Sushi x, y and z, respectively. If x, y and z are all different, A, B and C eats Sushi x, y and z, respectively. Otherwise, a fight brakes out.

You are given A's and B's preferences, (a_1,\ ...,\ a_N) and (b_1,\ ...,\ b_N). How many preferences of C, (c_1,\ ...,\ c_N), leads to all the pieces of sushi being consumed without a fight? Find the count modulo 10^9+7.

Constraints

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

Input

Input is given from Standard Input in the following format:

N
a_1 ... a_N
b_1 ... b_N

Output

Print the number of the preferences of C that leads to all the pieces of sushi being consumed without a fight, modulo 10^9+7.


Sample Input 1

3
1 2 3
2 3 1

Sample Output 1

2

The answer is two, (c_1,\ c_2,\ c_3) = (3,\ 1,\ 2),\ (3,\ 2,\ 1). In both cases, A, B and C will eat Sushi 1, 2 and 3, respectively, and there will be no more sushi.


Sample Input 2

3
1 2 3
1 2 3

Sample Output 2

0

Regardless of what permutation (c_1,\ c_2,\ c_3) is, A and B will try to eat Sushi 1, resulting in a fight.


Sample Input 3

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

Sample Output 3

80

For example, if (c_1,\ c_2,\ c_3,\ c_4,\ c_5,\ c_6) = (5,\ 1,\ 2,\ 6,\ 3,\ 4), A, B and C will first eat Sushi 1, 2 and 5, respectively, then they will eat Sushi 3, 4 and 6, respectively, and there will be no more sushi.


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