I. Hori and Cake
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Hori-san is eating a yummy cake baked for her by Miyamura. The cake is a strange cake that can be represented by a collection of line segments. Hori will take one or more bites in order to eat the cake.

In any bite, Hori can choose any segment and eat that segment as well as any segments that are fully contained within the segment.

It is guaranteed that all endpoints of segments are distinct. In addition, if two segments intersect, it is guaranteed that one of them will fully contain the other.

How many different sequences of bites are there for Hori to eat the entire cake (no segments left) modulo $$$10^9+7$$$?

Input

The first line has a single integer $$$T$$$, ($$$1 \le T \le 5 \cdot 10^3$$$) the number of test cases.

The first line of each test case has a single integer $$$N$$$, ($$$1 \le N \le 5 \cdot 10^3$$$). The next $$$N$$$ lines contain $$$l_i$$$ and $$$r_i$$$, $$$1 \le l_i \lt r_i \le 2N$$$, denoting the left and right endpoints of the segments. It is guaranteed that the sum of $$$N$$$ over all test cases won't exceed $$$5 \cdot 10^3$$$.

Output

For each test case, a single integer representing the number of sequences modulo $$$10^9 + 7$$$.

Example
Input
6
1
1 2
2
1 4
2 3
2
1 2
3 4
3
1 2
3 6
4 5
3
1 6
2 5
3 4
19
5 6
15 16
26 35
29 32
11 12
22 23
27 28
14 25
8 9
30 31
17 20
1 36
37 38
21 24
3 10
4 7
33 34
18 19
2 13
Output
1
2
2
5
4
585868918
Note

In the first test case, since there is only $$$1$$$ segment, there is only $$$1$$$ sequence of bites Hori can take to eat all segments.

In the second test case, Hori can either eat $$$[[1, 4]]$$$ or $$$[[2, 3], [1, 4]]$$$. In the first sequence, eating $$$[1, 4]$$$ would also make $$$[2, 3]$$$ disappear.

In the fifth test case, Hori can eat the following sequences.

  1. $$$[[3, 4], [2, 5], [1, 6]]$$$
  2. $$$[[3, 4], [1, 6]]$$$
  3. $$$[[2, 5], [1, 6]]$$$
  4. $$$[[1, 6]]$$$