← 返回题目列表

AtCoder · abc214_g

G. 三种排列

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

分数: 600 点

问题陈述

给出的是以下排列 (1, \dots, N): p = (p_1, \dots, p_N) 和 q = (q_1, \dots, q_N).

求模数 (10^9 + 7),排列 r = (r_1, \dots, r_N) of (1, \dots, N) 这样 r_i \neq p_i 和 r_i \neq q_i 对于每个 i (1 \leq i \leq N).

约束

  • 1 \leq N \leq 3000
  • 1 \leq p_i, q_i \leq N
  • p_i \neq p_j \, (i \neq j)
  • q_i \neq q_j \, (i \neq j)
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N
p_1 \ldots p_N
q_1 \ldots q_N

输出

打印答案。


示例输入 1

4
1 2 3 4
2 1 4 3

示例输出 1

4

有四种有效排列: (3, 4, 1, 2), (3, 4, 2, 1), (4, 3, 1, 2),和 (4, 3, 2, 1).


示例输入 2

3
1 2 3
2 1 3

示例输出 2

0

答案可能是 0.


示例输入 3

20
2 3 15 19 10 7 5 6 14 13 20 4 18 9 17 8 12 11 16 1
8 12 4 13 19 3 10 16 11 9 1 2 17 6 5 18 7 14 20 15

示例输出 3

803776944

请务必打印模数计数 (10^9 + 7).