## INTDSET - Chiaki With Intervals

Chiaki has a set $A$ of $n$ intervals, the $i$-th of them is $[l_i, r_i]$. She would like to know the number of such interval sets $S \subset A$: for every interval $a \in A$ which is not in $S$, there exists at least one interval $b$ in $S$ which has non-empty intersection with $a$. As this number may be very large, Chiaki is only interested in its remainder modulo $(10^9+7)$.

Interval $a$ has intersection with interval $b$ if there exists a real number $x$ that $l_a \le x \le r_a$ and $l_b \le x \le r_b$.

### Input

There are multiple test cases. The first line of input contains an integer $T$, indicating the number of test cases. For each test case:

The first line contains an integer $n$ ($1 \le n \le 2 \times 10^5$) -- the number of intervals.

Each of the following $n$ lines contains two integers $l_i$ and $r_i$ ($1 \le l_i < r_i \le 10^9$) denoting the $i$-th interval.

It is guaranteed that for every $1 \le i < j \le n$, $l_i \ne l_j$ or $r_i \ne r_j$ and that the sum of $n$ in all test cases does not exceed $2 \times 10^5$.

### Output

For each test case, output an integer denoting the answer.

### Example

#### Input:

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

#### Output:

1 7

hide comments

shubham_001:
2018-01-06 06:56:39
How answer of first test case is 1? when there is no intersection between any two intervals? |

Added by: | zimpha |

Date: | 2018-01-04 |

Time limit: | 1s |

Source limit: | 50000B |

Memory limit: | 1536MB |

Cluster: | Cube (Intel G860) |

Languages: | All |