There are $n$ points (not necessary distinct) on the plane. Suppose that each point $(x_i,y_i)$ has an associated probability of existence $p_i\in (0, 1]$.

For a point set $S=\{(x_1,y_1), (x_2,y_2), ..., (x_m,y_m)\}$, define $F(S)$ as the number of integer points $(x,y)$ that: there exists at least one index $i$ that $0 < x ≤ x_i$ and $0 < y ≤ y_i$.

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 ≤ 10^5)$ -- the number of points.

Each of the next $n$ lines contains four integers $x_i, y_i, a_i$ and $b_i\ (1 ≤ x_i, y_i≤ 10^9,\ 1 ≤ a_i≤ b_i≤ 10^9)$, where $p_i=\frac{a_i}{b_i}$.

It is guaranteed that the sum of all $n$ does not exceed $10^6$.

For each test case, output the answer as a value of a rational number modulo $10^9+ 7$.

Formally, it is guaranteed that under given constraints the probability is always a rational number $\frac{p}{q}$ ($p$ and $q$ are integer and coprime, $q$ is positive), such that $q$ is not divisible by $10^9+ 7$. Output such integer a between $0$ and $10^9+ 6$ that $p - aq$ is divisible by $10^9+ 7$.