K. Keeping A Secret
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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?

Input

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

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

Example
Input
9
1 1
2 3
2 3
2 5
3 6
3 7
3 8
3 8
3 9
Output
336
Note

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.