Farmer John has N cows on his farm (2≤N≤2⋅105), conveniently numbered 1…N
. Cow i is located at integer coordinates (xi,yi) (1≤xi,yi≤N). Farmer John wants to pick two teams for a game of mooball!
One of the teams will be the "red" team; the other team will be the "blue" team. There are only a few requirements for the teams. Neither team can be empty, and each of the N cows must be on at most one team (possibly neither). The only other requirement is due to a unique feature of mooball: an infinitely long net, which must be placed as either a horizontal or vertical line in the plane at a non-integer coordinate, such as x=0.5. FJ must pick teams so that it is possible to separate the teams by a net. The cows are unwilling to move to make this true.
Help a farmer out! Compute for Farmer John the number of ways to pick a red team and a blue team satisfying the above requirements, modulo 109+7.
INPUT FORMAT (input arrives from the terminal / stdin):
The first line of input contains a single integer N.
The next N lines of input each contain two space-separated integers xi and yi. It is guaranteed that the xi form a permutation of 1…N, and same for the yi.
OUTPUT FORMAT (print output to the terminal / stdout):
A single integer denoting the number of ways to pick a red team and a blue team satisfying the above requirements, modulo 109+7.
SAMPLE INPUT:
2
1 2
2 1
SAMPLE OUTPUT:
2
We can either choose the red team to be cow 1 and the blue team to be cow 2, or the other way around. In either case, we can separate the two teams by a net (for example, x=1.5).
SAMPLE INPUT:
3
1 1
2 2
3 3
SAMPLE OUTPUT:
10
Here are all ten possible ways to place the cows on teams; the ith character denotes the team of the ith cow, or . if the ith cow is not on a team.
RRB
R.B
RB.
RBB
.RB
.BR
BRR
BR.
B.R
BBR
SAMPLE INPUT:
3
1 1
2 3
3 2
SAMPLE OUTPUT:
12
Here are all twelve possible ways to place the cows on teams:
RRB
R.B
RBR
RB.
RBB
.RB
.BR
BRR
BR.
BRB
B.R
BBR
SAMPLE INPUT:
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
SAMPLE OUTPUT:
441563023
Make sure to output the answer modulo 109+7.
SCORING:
Input 5: N≤10
Inputs 6-9: N≤200
Inputs 10-13: N≤3000
Inputs 14-24: No additional constraints.
Problem credits: Dhruv Rohatgi
扫码领取USACO试题答案+详细解析
咨询一对一备赛规划
