## USACO 2024 January Contest, Platinum

## Problem 3. Mooball Teams III

Contest has ended.

**Log in to allow submissions in analysis mode**

Farmer John has $N$ cows on his farm ($2 \leq N \leq 2\cdot 10^5$), conveniently numbered $1 \dots N$. Cow $i$ is located at integer coordinates $(x_i, y_i)$ ($1\le x_i,y_i\le 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 $10^9+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 $x_i$ and $y_i$. It is guaranteed that the $x_i$ form a permutation of $1\dots N$, and same for the $y_i$.

#### 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 $10^9+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 $i$th character denotes the team of the $i$th cow, or . if the $i$th 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 $10^9+7$.

#### SCORING:

- Input 5: $N\le 10$
- Inputs 6-9: $N\le 200$
- Inputs 10-13: $N\le 3000$
- Inputs 14-24: No additional constraints.

Problem credits: Dhruv Rohatgi