405466: GYM101968 B Rectangles

You are given $$$2n$$$ points, you need to pair them to create $$$n$$$ rectangles so that the intersection of all those rectangles forms a positive area. In how many ways you can do that? Find the number of ways modulo $$$10^9+7$$$.

Pairing two points ($$$x1,y1$$$) and ($$$x2,y2$$$) forms the rectangle with bottom-left corner ($$$min(x1, x2), min(y1, y2)$$$) and top-right corner ($$$max(x1, x2), max(y1, y2)$$$).

The first line of input contains a single integer $$$T$$$ ($$$1 \le T \le 3200$$$), the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$), the number of rectangles you need to make.

The following $$$2n$$$ lines each contains two space-separated integers $$$x_i,y_i$$$ ($$$-10^9 \le x_i,y_i \le 10^9$$$), representing the coordinates of the $$$i^{th}$$$ point. All points are distinct.

The sum of $$$n$$$ over all test cases doesn't exceed $$$5\times10^5$$$.

For each test case output a single line with the number of ways to pair the $$$2n$$$ points modulo $$$10^9+7$$$.

2
2
0 0
0 1
1 0
1 1
2
0 1
1 0
2 3
3 2

1
2