#48 순열의 개수

문제

Statement language

양의 정수 $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])$ 의 순서쌍 의 개수를 로 나눈 나머지를 구하여라.

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

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

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

Sample 1

Input

2
2 1
2 1

Output

2

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

Sample 2

Input

3
1 2 3
1 2 3

Output

6

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

Sample 3

Input

5
1 2 3 4 5
1 2 3 5 4

Output

0

이 예제는 서브태스크 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

14

이 예제는 서브태스크 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의 조건을 만족한다.