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.”

- 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 T (1 ≤ T ≤ 10) denoting the count of testcase.

For each testcase,

The first line contains one integer n (1 ≤ n ≤ 100000) denoting the number of nodes in the tree.

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

It is guaranteed that $\sum n ≤ 5.1\times 10^5$.

For each testcase, output one line containing the number of trees modulo $10^9$ + 7.

1
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.

“红旗杯”第十五届黑龙江省大学生程序设计竞赛