Skyline

输入描述:

There are multiple test cases. The first line of input is an integer T indicates the number of test cases. For each test case:
The first line contains an integer n (1 ≤ n ≤ 105) -- the number of points.
Each of the next n lines contains four integers xi, yi, ai and bi (1 ≤ xi, yi ≤ 109, 1 ≤ ai ≤ bi ≤ 109), where .
It is guaranteed that the sum of all n does not exceed 106.

输出描述:

For each test case, output the answer as a value of a rational number modulo 109 + 7.
Formally, it is guaranteed that under given constraints the probability is always a rational number  (p and q are integer and coprime, q is positive), such that q is not divisible by 109 + 7. Output such integer a between 0 and 109 + 6 that p - aq is divisible by 109 + 7.

2
3
1 2 1 1
1 2 1 1
1 2 1 1
4
1 2 1 2
1 3 1 2
2 1 1 2
3 1 1 2

2
937500010