Moo Ball Teams

Farmer John has \(N\) cows (\(2 \le N \le 2\cdot10^5\)) on his farm. The \(i\)th cow is located at the integer coordinate \((x_i,y_i)\) with \(1 \le x_i,y_i \le N\). He wishes to form two teams to play the moo‐ball game: one designated the red team and the other the blue team. Each cow may be assigned to at most one team (or not chosen at all) but neither team may be empty.

The only other requirement stems from the unique way moo‐ball is played. An infinitely long net, which must be placed on the plane as either a horizontal or vertical line at a non‐integer coordinate (for example, \(x=0.5\)), must be able to separate the two teams. In other words, it must be possible to choose such a line so that all of the cows on one team lie entirely on one side of the line and all of the cows on the other team lie entirely on the opposite side. The cows will not move from their given positions.

Help Farmer John calculate, modulo \(10^9+7\), the number of ways to choose red and blue teams (i.e. assign some cows to red, some to blue, and leave the rest unassigned) that satisfy these conditions.

Note: The net can be placed either vertically at a line of the form \(x=k+0.5\) for some integer \(k\), or horizontally at a line of the form \(y=k+0.5\). Hence, a valid team assignment must be separable either by a vertical line or by a horizontal line.

inputFormat

The first line contains a single integer \(N\). The next \(N\) lines each contain two integers \(x_i\) and \(y_i\) representing the coordinates of the \(i\)th cow.

outputFormat

Output a single integer, which is the number of valid team assignments modulo \(10^9+7\).

sample

2
1 1
2 2

2