题目描述

3 名男性 A、B、C 决定一起吃寿司。最开始有 $N$ 种寿司，每种各有 1 个。寿司编号为 1 到 $N$。其中，$N$ 一定是 3 的倍数。

3 人各自对寿司有喜好排名。A 的排名用 1 到 $N$ 的一个排列 $(a_1, \ldots, a_N)$ 表示。对于每个 $i$（$1 \leq i \leq N$），A 最喜欢的第 $i$ 个寿司是寿司 $a_i$。同理，B 和 C 的排名分别用排列 $(b_1, \ldots, b_N)$ 和 $(c_1, \ldots, c_N)$ 表示。

只要寿司还剩下或者未发生争吵（见下述），3 个人就重复以下操作：

• A、B、C 各自从剩下的寿司中选出自己最喜欢的一种，分别记为 $x$、$y$、$z$。如果 $x$、$y$、$z$ 两两不同，则 A、B、C 分别吃掉寿司 $x$、$y$、$z$。否则，三人会开始争吵并打架。

给定 A 和 B 的排名 $(a_1, \ldots, a_N)$ 和 $(b_1, \ldots, b_N)$，请问 C 的排名 $(c_1, \ldots, c_N)$ 有多少种不同的排列，能使得三人无争吵地吃光所有寿司？请输出答案对 $10^9+7$ 取模后的结果。

输入格式

输入以如下格式从标准输入给出。

$N$ $a_1$ $\ldots$ $a_N$ $b_1$ $\ldots$ $b_N$

输出格式

输出能够使三人无争吵地吃光所有寿司的 C 的排名数目，对 $10^9+7$ 取模的结果。

输入输出样例 #1

输入 #1

3
1 2 3
2 3 1

输出 #1

2

输入输出样例 #2

输入 #2

3
1 2 3
1 2 3

输出 #2

0

输入输出样例 #3

输入 #3

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

输出 #3

80

输入输出样例 #4

输入 #4

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

输出 #4

160

输入输出样例 #5

输入 #5

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

输出 #5

33600

说明/提示

限制条件

• $3 \leq N \leq 399$
• $N$ 是 3 的倍数。
• $(a_1, \ldots, a_N)$ 和 $(b_1, \ldots, b_N)$ 是 1 到 $N$ 的全排列。

样例解释 1

$(c_1, c_2, c_3) = (3, 1, 2),\ (3, 2, 1)$ 一共有 2 种情况。此时三人会分别吃掉寿司 1、2、3，最终寿司全部被吃光。

样例解释 2

无论 $(c_1, c_2, c_3)$ 是哪种排列，A 和 B 都会同时选寿司 1，因此会发生争吵。

样例解释 3

例如对于 $(c_1, c_2, c_3, c_4, c_5, c_6) = (5, 1, 2, 6, 3, 4)$，第一次 A、B、C 分别吃掉寿司 1、2、5，第二次分别吃掉 3、4、6，寿司被全部吃完。