AT_abc214_g [ABC214G] Three Permutations

题目描述

给定 $(1,\dots,N)$ 的两个排列 $p = (p_1,\dots,p_N)$ 和 $q = (q_1,\dots,q_N)$。

请计算有多少个 $(1,\dots,N)$ 的排列 $r = (r_1,\dots,r_N)$，使得对于所有 $i\ (1 \leq i \leq N)$，都有 $r_i \neq p_i$ 且 $r_i \neq q_i$。请输出答案对 $10^9 + 7$ 取模的结果。

输入格式

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

$N$ $p_1$ $\ldots$ $p_N$ $q_1$ $\ldots$ $q_N$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

4
1 2 3 4
2 1 4 3

输出 #1

4

输入输出样例 #2

输入 #2

3
1 2 3
2 1 3

输出 #2

0

输入输出样例 #3

输入 #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

说明/提示

限制条件

• $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)$
• 输入均为整数。

样例解释 1

满足条件的有 $4$ 个排列，分别为 $(3,4,1,2)$、$(3,4,2,1)$、$(4,3,1,2)$、$(4,3,2,1)$。

样例解释 2

答案有可能为 $0$。

样例解释 3

请注意输出时需要对 $10^9 + 7$ 取模。

由 ChatGPT 4.1 翻译