Expected Bounding Box (Stretch)

This is a stretch problem.

There are $n$ points on the plane. Point $i$ has coordinates $(x_i, y_i)$ and is selected independently with probability $a_i / b_i$.

Let $S$ be the random set of selected points, and let $R$ be the smallest axis-aligned bounding rectangle containing every point of $S$. The geometric area of $R$ is

$(\max_{i \in S} x_i - \min_{i \in S} x_i) \cdot (\max_{i \in S} y_i - \min_{i \in S} y_i)$.

If $S$ has fewer than two points, or all selected points share the same $x$-coordinate or the same $y$-coordinate, this area is $0$.

Output the expected area of $R$.

It can be shown that the answer can be expressed as a rational number $P/Q$ in lowest terms with $Q$ coprime to $10^9 + 7$. Output $P \cdot Q^{-1} \bmod (10^9 + 7)$.

Input

The first line contains an integer $n$.

Each of the next $n$ lines contains four integers $x_i$, $y_i$, $a_i$, and $b_i$.

Output

Print a single integer: the expected area modulo $10^9 + 7$.

Constraints

• $1 \le n \le 2 \cdot 10^5$
• $-10^9 \le x_i, y_i \le 10^9$
• $0 \le a_i < b_i \le 10^9$

Example 1

2
0 0 1 2
1 1 1 2

250000002

Explanation

The bounding rectangle has area $1$ only if both points are selected, which happens with probability $1/4$. Otherwise the area is $0$.

Example 2

2
0 0 1 2
3 4 1 2

3

Explanation

Both points are selected with probability $1/4$, and then the area is $12$. The expected area is $3$.

Example 3

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

1

Explanation

Each subset of the three points is equally likely. The only non-degenerate rectangles come from selecting both $(2, 0)$ and $(0, 2)$ (area $4$), and from selecting all three points (area $4$). The expected area is therefore $1$.