You are in charge of a storage room, which is formed by two infinite diagonal walls joining in a single point at the bottom. There are $n$ equally sized square boxes in the storage. The boxes are naturally pulled by gravity. For example, the placement of the boxes could be as follows:
Then the bottom box is removed from the storage. The other boxes start to fall into the now empty space until a stable arrangement is reached again. The boxes can fall in different ways, depending on whether the left or the right upper box fills the empty slot. For example, in the previous figure, there are 3 different options:
Find the total number of different possible falling scenarios modulo $10^9 + 7$.
The first line contains a single integer, the number of boxes $n$ ($1 <= n <= 10^5$). The next $n$ lines describe the boxes, the $i$-th of them contains two integers $x_i$ and $y_i$ ($1 <= x_i, y_i <= n$). These are the coordinates of the box in the following system: the rows of boxes perpendicular to the left storage wall are numbered by integers starting from $1$ and we denote this axis by $x$; the rows of boxes perpendicular to the right storage wall are numbered by integers starting from $1$ and we denote this axis by $y$. The box at coordinates $(x_i, y_i)$ is located at the intersection of the $x_i$-th and $y_i$-th such rows, accordingly.
It is guaranteed that the given arrangement of boxes is stable.
Output a single integer, the number of possible scenarios of falling boxes modulo $10^9 + 7$.
## Input
The first line contains a single integer, the number of boxes $n$ ($1 <= n <= 10^5$). The next $n$ lines describe the boxes, the $i$-th of them contains two integers $x_i$ and $y_i$ ($1 <= x_i, y_i <= n$). These are the coordinates of the box in the following system: the rows of boxes perpendicular to the left storage wall are numbered by integers starting from $1$ and we denote this axis by $x$; the rows of boxes perpendicular to the right storage wall are numbered by integers starting from $1$ and we denote this axis by $y$. The box at coordinates $(x_i, y_i)$ is located at the intersection of the $x_i$-th and $y_i$-th such rows, accordingly. It is guaranteed that the given arrangement of boxes is stable.
## Output
Output a single integer, the number of possible scenarios of falling boxes modulo $10^9 + 7$.
[samples]
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the number of boxes.
Let $ B = \{ (x_i, y_i) \mid i \in \{1, \dots, n\} \} $ be the set of box coordinates, where $ x_i, y_i \in \{1, \dots, n\} $, representing positions along two diagonal axes.
**Constraints**
1. $ 1 \le n \le 10^5 $
2. The set $ B $ forms a stable arrangement under gravity: for every box at $ (x, y) \in B $ with $ x > 1 $ and $ y > 1 $, the boxes at $ (x-1, y) $ and $ (x, y-1) $ must also be in $ B $.
3. The bottom box (i.e., the box with minimal $ x+y $, and uniquely determined by stability) is removed.
**Objective**
Compute the number of distinct sequences of box falls (each fall being a box sliding down-left or down-right into an empty space) that result in a stable configuration after the removal of the bottom box, modulo $ 10^9 + 7 $.
This is equivalent to counting the number of linear extensions of the poset induced by the box arrangement (with partial order defined by dominance: box $ (x,y) $ must fall after boxes $ (x+1,y) $ and $ (x,y+1) $), after removing the minimal element.
Let $ P $ be the poset on $ B \setminus \{(x_0, y_0)\} $, where $ (x_0, y_0) $ is the bottom box, and $ (a,b) \prec (c,d) $ iff $ a \le c $, $ b \le d $, and $ (a,b) \ne (c,d) $.
The number of valid falling scenarios is the number of linear extensions of $ P $.