题目描述

$(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$

输出格式

答えを出力せよ。

题目大意

给出两个大小为 $n$ 的排列 $p,q$，你需要求出大小为 $n$ 的排列 $r$ 的数量，使得 $r_i\neq p_i,r_i\neq q_i$。

4
1 2 3 4
2 1 4 3

4

3
1 2 3
2 1 3

0

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

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)$
• 入力は全て整数である。

Sample Explanation 1

$ (3,\ 4,\ 1,\ 2),\ (3,\ 4,\ 2,\ 1),\ (4,\ 3,\ 1,\ 2),\ (4,\ 3,\ 2,\ 1) $ の $4$ つが条件を満たします。

Sample Explanation 2

答えが $0$ になることもあります。

Sample Explanation 3

$(10^9\ +\ 7)$ で割った余りを出力することに注意してください。