문제
운동장에
정올이는 피구 게임을 위해 두 팀을 뽑으려고 한다! 하나의 팀은 "빨간" 팀이고, 다른 팀은 "파란" 팀이다. 팀을 뽑을 때 몇 가지 조건이 있다.
두 팀은 비어 있을 수 없고, 각 학생은 최대한 한 팀에만 속할 수 있다 (혹은 어느 팀에도 속하지 않을 수 있다).
무한히 긴 네트를 설치해야 하는데, 네트는 수평선 또는 수직선으로 놓을 수 있으며, 반드시 정수 좌표가 아닌 위치 (예:
x = 0.5 )에 놓여야 한다.
정올이는 두 팀을 뽑고, 그 팀들을 네트로 분리할 수 있는 방법이 몇 가지 있는지 계산해야 한다. 이 값은10^9 + 7 로 나눈 나머지를 구하시오.
입력
첫 번째 줄에 정수
그 다음
[제약 조건]
2 \leq N \leq 2 \cdot 10^5 1 \leq x_i, y_i \leq N
출력
두 팀을 뽑을 수 있는 방법의 수를
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 15점 | |
| #2 | 20점 | |
| #3 | 35점 | |
| #4 | 30점 | 추가 제약 조건 없음 |
예제 #1
2
1 2
2 1
2
이 경우, 빨간 팀을 학생 1번, 파란 팀을 학생 2번으로 뽑거나 그 반대로 뽑을 수 있습니다. 두 팀은 예를 들어
예제 #2
3
1 1
2 2
3 3
10
이 경우 가능한 10가지 방법은 다음과 같습니다:
RRB
R.B
RB.
RBB
.RB
.BR
BRR
BR.
B.R
BBR예제 #3
3
1 1
2 3
3 2
12
이 경우 가능한 12가지 방법은 다음과 같습니다:
RRB
R.B
RBR
RB.
RBB
.RB
.BR
BRR
BR.
BRB
B.R
BBR예제 #4
40
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
10 10
11 11
12 12
13 13
14 14
15 15
16 16
17 17
18 18
19 19
20 20
21 21
22 22
23 23
24 24
25 25
26 26
27 27
28 28
29 29
30 30
31 31
32 32
33 33
34 34
35 35
36 36
37 37
38 38
39 39
40 40
441563023
로그인해야 코드를 작성할 수 있어요.