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