/ 
Time Limit: 2 sec / Memory Limit: 512 MB
配点 : 1800 点
問題文
3 人の男性 A, B, C が一緒に寿司を食べることになりました。 最初、N 種類の寿司が 1 個ずつあります。 寿司には 1 から N まで番号が振られています。 ただし、N は 3 の倍数とします。
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
- N は 3 の倍数である。
- (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