← 返回题目列表

AtCoder · code_festival_2017_qualc_f

F. 三个贪吃者

中文机器翻译题面 查看原题

分数: 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