配点 : 600 点
問題文
(1,…,N) の順列 p=(p1,…,pN),q=(q1,…,qN) が与えられます。
(1,…,N) の順列 r=(r1,…,rN) であって、全ての i(1≤i≤N) に対し ri=pi かつ ri=qi となるようなものの総数を (109+7) で割った余りを求めてください。
制約
- 1≤N≤3000
- 1≤pi,qi≤N
- pi=pj(i=j)
- qi=qj(i=j)
- 入力は全て整数である。
入力
入力は以下の形式で標準入力から与えられる。
N
p1 … pN
q1 … qN
出力
答えを出力せよ。
4
1 2 3 4
2 1 4 3
4
$(3, 4, 1, 2), (3, 4, 2, 1), (4, 3, 1, 2), (4, 3, 2, 1)$ の 4 つが条件を満たします。
3
1 2 3
2 1 3
0
答えが 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
(109+7) で割った余りを出力することに注意してください。