9124: Non-Puzzle: Segment Pair

There are $n$ pairs of segments in the X-axis. The $i$-th of them is [li,ri][l_{i},r_{i}][li,ri] and [li′,ri′][l'_{i},r'_{i}][li′,ri′].

You should choose exactly one segment from each pair (that is, choose either [li,ri][l_{i},r_{i}][li,ri] or [li′,ri′][l'_{i},r'_{i}][li′,ri′] for each $i$), satisfying that there exists at least one point $x$, which is included by all the chosen segments.

You need to determine the number of different ways of choosing the segments (over 2n2^n2n possible ways) that satisfies the condition, output it modulo 109+710^9+7109+7.

Two ways are considered different if and only if there exists $i$, such that [li,ri][l_{i},r_{i}][li,ri] is chosen in one way, and [li′,ri′][l'_{i},r'_{i}][li′,ri′] is chosen in another. Note that even if [li,ri]=[li′,ri′][l_{i},r_{i}] = [l'_{i},r'_{i}][li,ri]=[li′,ri′], the two ways are considered different.

The first line contains one integer $n$(1≤n≤5⋅1051\le n \le 5\cdot 10^51≤n≤5⋅105).
The following $n$ lines, each line contains four integers li,ri,li′,ri′l_{i},r_{i},l'_{i},r'_{i}li,ri,li′,ri′(1≤li≤ri≤5⋅1051\le l_{i} \le r_{i} \le 5\cdot 10^51≤li≤ri≤5⋅105 , 1≤li′≤ri′≤5⋅1051\le l'_{i} \le r'_{i} \le 5\cdot 10^51≤li′≤ri′≤5⋅105).

Output a single integer, representing the number of different ways of choosing the segments, modulo 109+710^9+7109+7.

3
1 4 6 7
2 5 3 5
1 3 5 7

2