407507: GYM102803 K Keeping A Secret

Little Y is a Riddler. He always says that this is a secret.

One day, he got a undirected tree. He met Jessica and say, "Hey! I've got a new tree. Do you want to guess? This is a secret."

"This is a tree with $$$n$$$ nodes. Each node has three restrictions and two parameters $$$d_i$$$ and $$$x_i$$$."

• The depth of node $$$i$$$ in the tree is $$$d_i$$$.
• The position of $$$i$$$ in the BFS sequence of tree should be less than or equal to $$$x_i$$$.
• If $$$x$$$ is before $$$y$$$ in BFS sequence, either the parent node of $$$x$$$ is also the parent node of $$$y$$$, or the parent node of $$$x$$$ is before the parent node of $$$y$$$ in BFS sequence.

However, Jessica quickly finds that too many trees satisfy his conditions. To give him a lesson, she wants to figure out the number of the trees satisfying all these restrictions. Can you help her?

The first line contains one integer $$$n ~ (1 \leq n \leq 100\,000)$$$ denoting the number of nodes in the tree.

The next $$$n$$$ lines each contains contains two integer $$$d_i, x_i ~ (1 \leq d_i, x_i \leq n)$$$ denoting the restriction of node $$$i$$$.

Output one line containing the number of trees modulo $$$10^9+7$$$.

9
1 1
2 3
2 3
2 5
3 6
3 7
3 8
3 8
3 9

336

The depth of root is $$$1$$$.

Note that the BFS sequence of following two trees are different. They are $$$1-2-3$$$ and $$$1-3-2$$$ respectively.