Mooball Teams III
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.
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).
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
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
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
Source: USA Computing Olympiad.
Input Format
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
A single integer denoting the number of ways to pick a red team and a blue team satisfying the above requirements, modulo 109+7.