The first night, then, I went to sleep on the sand, a thousand miles from any human. I was more isolated than a shipwrecked sailor on a raft in the middle of the ocean. Thus you can imagine my amazement, at sunrise, when I was awakened by an odd little voice. It said:

“If you please--draw me a mountain range!”

“What?”

“Draw me a mountain range!”

Not knowing what to draw, as a big person who has lost all his sense of creativity to IB Math and Science classes, I first drew a coordinate plane with \(N\) dots on it.

“No, no, no! I do not want \(N\) dots on a sheet of paper! I already see enough dots by just looking up at the sky where I live. What I need is a mountain range. Draw me a mountain range!"

So then I made a drawing.

Unfortunately, despite intense searching, you’ve never been able to find the pilot’s final drawing: all you’ve managed to find are the precise locations of each of the \(N\) dots. You know that the pilot drew the mountain range by connecting at least three dots such that:

1. Each dot is connected to exactly one or two dots. A dot that is connected to exactly one other dot is known as an endpoint.
2. If a dot is connected to two other dots, its \(x\)-coordinate must be strictly greater than the \(x\)-coordinate of one of the dots it is connected to and strictly smaller than the \(x\)-coordinate of the other dot it is connected to.
3. A dot that is connected to two other dots is either a peak or a trough. For a dot to be a peak, its \(y\)-coordinate must be strictly greater than the \(y\)-coordinates of both of the dots it is connected to. For a dot to be a trough, its \(y\)-coordinate must be strictly smaller than the \(y\)-coordinates of both of the dots it is connected to.

An example of a valid mountain range is shown below. Endpoints are shown in black, peaks are shown in red and troughs are shown in blue.

As you are unable to find the exact mountain range in the pilot’s final drawing, you content yourself with finding the number of unique mountain ranges the pilot could have drawn. As this number can be very big, you are satisfied with finding the remainder when the number of unique mountain ranges is divided by \(10^9+7\). Two mountain ranges are considered different if there is at least one dot that is used in one mountain range but not the other.

(The Folklore is an edited extract from Chapter 2 of Le Petit Prince by Antoine de Saint-Exupéry and is in no way affiliated with CBOJ.)

Addendum: For this problem, it is highly recommended to use Python 2/3 rather than PyPy 2/3.

Input Specification

The first line will contain the integer \(N\), the number of dots the pilot has drawn. The next \(N\) lines will each contain two space separated integers, \(x_i\) and \(y_i\), representing the coordinates of the \(i\)-th dot. It is guaranteed that there exists no pair of points \(\{i,\,j \}\) such that \(x_i = x_j\) AND \(y_i=y_j\).

Output Specification

Output one integer, the remainder when the number of unique mountain ranges the pilot could have drawn is divided by \(10^9+7\).

Input Constraints

Subtask 1 [5%]

\(1 \leq N \leq 20\)

\(1 \leq x_i, y_i \leq 10^6\)

Subtask 2 [15%]

\(1 \leq N \leq 10^3\)

\(1 \leq x_i, y_i \leq 10^6\)

Subtask 3 [40%]

\(1 \leq N \leq 5\times 10^4\)

\(1 \leq x_i, y_i \leq 10^6\)

Subtask 4 [40%]

\(1 \leq N \leq 5\times 10^4\)

\(-10^9 \leq x_i, y_i \leq 10^9\)

Sample Input 1

5
4 9
1 5
4 7
7 1
13 5

Sample Output 1

9

Explanation of Sample 1

The pilot’s mountain ranges could have connected points \(\{2,1,4\}\), \(\{2,1,4,5\}\), \(\{2,1,5\}\), \(\{2,3,4\}\), \(\{2,3,4,5\}\), \(\{2,3,5\}\), \(\{2,4,5\}\), \(\{1,4,5\}\), or \(\{3,4,5\}\), yielding \(9\) possible mountain ranges. The remainder when \(9\) is divided by \(10^9+7\) is still \(9\), which is outputted.