5068: 排列

内存限制:512 MB 时间限制:1.000 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:3 通过:2

题目描述

    给你$2$个对于$1$到$N$的排列: 
    $$p=(p_1,p_2,...,p_N) $$
    $$q=(q_1,q_2,...,q_N) $$
    现在你需要找出有多少个排列$r=(r_1,r_2,...,r_N)$,使得对于任意$i(1 \leq i \leq N)$,有$r_i \neq p_i \ and \ r_i \neq q_i$,由于这样的排列很多,请对$10^9+7$取模。 

输入格式

输入的第一行是一个整数$N$,表示数的个数。 
接下来一行有$N$个数,表示排列$p=(p_1,p_2,...,p_N)$。 
接下来一行有$N$个数,表示排列$q=(q_1,q_2,...,q_N)$。 

输出格式

输出只有一个非负整数,表示排列$r$的数量,对$10^9+7$取模。 

输入样例 复制

#1: 
4
1 2 3 4
2 1 4 3

#2:
3
1 2 3
2 1 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

输出样例 复制

#1:
4

#2: 
0

#3:
803776944

数据范围与提示

对于$50\%$的数据,$1 \leq N \leq 20$。 
对于$100\%$的数据,$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) $。