問題文

$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