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 \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 翻译