时间限制：C/C++/Rust/Pascal 10秒，其他语言20秒
空间限制：C/C++/Rust/Pascal 128 M，其他语言256 M
64bit IO Format: %lld
空间限制：C/C++/Rust/Pascal 128 M，其他语言256 M
64bit IO Format: %lld
题目描述
There are n points (not necessary distinct) on the plane. Suppose that each point (xi,yi) has an associated probability of existence pi ∈ (0, 1].
For a point set S={(x1,y1), (x2,y2), ..., (xm,ym)}, define F(S) as the number of integer points (x,y) that: there exists at least one index i that 0 < x ≤ xi and 0 < y ≤ yi.
Chiaki would like to know the expectation of F(S) of the n stochastic points.
For a point set S={(x1,y1), (x2,y2), ..., (xm,ym)}, define F(S) as the number of integer points (x,y) that: there exists at least one index i that 0 < x ≤ xi and 0 < y ≤ yi.
Chiaki would like to know the expectation of F(S) of the n stochastic points.
输入描述:
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.