Mooball Teams III

Time limit2sMemory limit1024 MB

Summary

Count pairs of nonempty, disjoint red and blue cow sets that one horizontal or vertical net at a half-integer coordinate separates, modulo 1e9+7.

Level: Medium7 of 10
Topics: Combinatorics, Math, Implementation
Solved: No attempts yet

Problem

Farmer John has $N$ cows on his farm ( $2 \leq N \leq 2\cdot 10^5$ ), 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 team is the "red" team and the other is the "blue" team. Neither team can be empty, and each cow may be on at most one team (or on neither). Mooball has one more rule. An infinitely long net must be placed as either a horizontal or vertical line at a non-integer coordinate, such as $x = 0.5$ , and the two teams must be separated by that net. The cows will not move to make this true.

Count the ways to pick a red team and a blue team that satisfy these conditions, modulo $10^9+7$ .

Input

The first line contains a single integer $N$ .

Each of the next $N$ lines contains two space-separated integers $x_i$ and $y_i$ . The $x_i$ form a permutation of $1 \dots N$ , and the $y_i$ form a permutation of $1 \dots N$ .

Output

Print a single integer: the number of ways to pick a red team and a blue team that satisfy the conditions, modulo $10^9+7$ .

Examples4

Example 1
Input
```
2
1 2
2 1
```
Expected output
```
2
```
Example 2
Input
```
3
1 1
2 2
3 3
```
Expected output
```
10
```
Example 3
Input
```
3
1 1
2 3
3 2
```
Expected output
```
12
```

Example 4

Input

Expected output

441563023