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

Input

2
0 0 1 2
1 1 1 2

Output

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

Input

2
0 0 1 2
3 4 1 2

Output

3

Explanation

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

Example 3

Input

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

Output

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~.