407648: GYM102862 L Falling Boxes

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 \leq n \leq 10^5$$$). The next $$$n$$$ lines describe the boxes, the $$$i$$$-th of them contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \leq x_i, y_i \leq 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$$$.

5
1 1
1 2
2 2
3 1
2 1

3