#48 순열의 개수

問題を読み込み中...

本文、提出履歴、提出フォームを準備しています。

作問者: pk661

Statement

問題文の言語

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

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

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

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

#	得点	制約
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	추가적인 제약조건이 없다.

例 1

入力例

2
2 1
2 1

出力例

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

例 2

入力例

3
1 2 3
1 2 3

出力例

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

例 3

入力例

5
1 2 3 4 5
1 2 3 5 4

出力例

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

例 4

入力例

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

出力例

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

例 5

入力例

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

出力例

3360

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