分数: 1800 点
问题陈述
A、B、C 三个男人正在一起吃寿司。 最初,有 N 寿司片,已编号 1 通过 N。 在这里, N 是以下的倍数 3.
三人对寿司各有好恶。 A的偏好表示为 (a_1,\ ...,\ a_N),整数的排列 1 to N。 对于每个 i (1 \leq i \leq N),A i- 最喜欢的寿司是寿司 a_i。 类似地,B 和 C 的偏好由下式表示: (b_1,\ ...,\ b_N) 和 (c_1,\ ...,\ c_N),整数的排列 1 to N.
三人重复以下动作,直到吃完所有寿司或战斗停止(稍后描述):
- A、B、C 三人各自在剩下的寿司中找到了自己最喜欢的寿司。让这些碎片成为寿司 分别是 x, y 和 z。如果 x, y 和 z 都不同,A、B、C 吃寿司 分别是 x, y 和 z。否则,一场战斗就会结束。
你有 A 和 B 的偏好, (a_1,\ ...,\ a_N) 和 (b_1,\ ...,\ b_N)。 C有多少个偏好, (c_1,\ ...,\ c_N),导致寿司不战而散? 求计数模数 10^9+7.
约束
- 3 \leq N \leq 399
- N 是以下的倍数 3.
- (a_1,\ ...,\ a_N) 和 (b_1,\ ...,\ b_N) 是以下整数的排列 1 to N.
输入
输入由标准输入按以下格式给出:
N a_1 ... a_N b_1 ... b_N
输出
打印 C 导致所有寿司都被不打架地吃掉的偏好数量,取模 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)。 在这两种情况下,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,然后他们会分别吃寿司 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