#48 permutation

Loading problem...

Preparing the statement, recent submissions, and submit form.

#48 permutation | DOJ

DOJ/DOJ Contest/DOJ Contest 2

Authors: pk661

Time limit: 2000 ms
Memory limit: 1024 MB
Checker: CUSTOM
Solve threshold: 100

Statement

KO EN

양의 정수 $N$ 과 $(1, 2, \cdots, N)$ 의 순열 $A = (a[1], a[2], \cdots, a[N]), B = (b[1], b[2], \cdots, b[N])$ 이 주어진다.

모든 $1 \leq i \leq N$ 에 대하여

p[q[i]] = a[i], \quad q[p[i]] = b[i]

를 만족하는 순열 $P = (p[1], p[2], \cdots, p[N]), Q = (q[1], q[2], \cdots, q[N])$ 의 순서쌍 $(P, Q)$ 의 개수를 $10^9 + 7$ 로 나눈 나머지를 구하여라.

Input

입력은 다음과 같은 형식으로 주어진다.

$N$ $a[1] \ a[2] \ \cdots \ a[N]$ $b[1] \ b[2] \ \cdots \ b[N]$

Output

첫째 줄에 정답을 출력한다.

Constraints

$1 \leq N \leq 200 \ 000$ .
$1 \leq a[i] \leq N$ ( $1 \leq i \leq N$ ).
$1 \leq b[i] \leq N$ ( $1 \leq i \leq N$ ).
$a[i] \neq a[j]$ ( $1 \leq i < j \leq N$ ).
$b[i] \neq b[j]$ ( $1 \leq i < j \leq N$ ).

Subtasks

#	Score	Constraints
1	5	$N \leq 6$ .
2	9	$N \leq 10$ .
3	12	$a[i] = i$ ( $1 \leq i \leq N$ ).
4	15	$a[i] = i + 1$ ( $1 \leq i \leq N - 1$ ). $a[N] = 1$ .
5	10	$a[i] \neq i$ ( $1 \leq i \leq N$ ). $b[i] \neq i$ ( $1 \leq i \leq N$ ). $a[a[i]] = i$ ( $1 \leq i \leq N$ ). $b[b[i]] = i$ ( $1 \leq i \leq N$ ).
6	11	$a[a[i]] = i$ ( $1 \leq i \leq N$ ). $b[b[i]] = i$ ( $1 \leq i \leq N$ ).
7	17	$a[i] = b[i]$ ( $1 \leq i \leq N$ ).
8	14	$N \leq 5 \ 000$ .
9	7	추가적인 제약조건이 없다.

Samples

Sample 1

Input

2
2 1
2 1

Output

이 예제는 서브태스크 1, 2, 4, 5, 6, 7, 8, 9의 조건을 만족한다.

Sample 2

Input

3
1 2 3
1 2 3

Output

이 예제는 서브태스크 1, 2, 3, 7, 8, 9의 조건을 만족한다.

Sample 3

Input

5
1 2 3 4 5
1 2 3 5 4

Output

이 예제는 서브태스크 1, 2, 3, 6, 8, 9의 조건을 만족한다.

Sample 4

Input

9
6 9 1 7 8 4 2 5 3
6 9 1 7 8 4 2 5 3

Output

이 예제는 서브태스크 2, 7, 8, 9의 조건을 만족한다.

Sample 5

Input

23
3 19 20 15 16 18 11 13 4 21 5 9 1 2 12 14 22 10 7 8 6 23 17
14 16 5 15 11 2 9 20 12 1 18 23 4 10 17 19 8 21 6 22 3 13 7

Output

3360

이 예제는 서브태스크 8, 9의 조건을 만족한다.

순열의 개수

Statement

Input

Output

Constraints

Subtasks

Samples