Problem Description

There is a set of intervals, the size of this set is $n$.

If we select a subset of this set with equal probability, how many the expected length of intervals' union of this subset is?

We assume that the length of empty set's union is 0, and we want the answer multiply $2^n$ modulo $10^9 + 7$.

Input

The first line of the input is a integer $T$, meaning that there are $T$ test cases.

Every test cases begin with a integer $n$ ,which is size of set.

Then $n$ lines follow, each contain two integers $l , r$ describing a interval of $[l , r]$.

$1 \leq n \leq 100,000$.

$-1,000,000,000 \leq l \leq r \leq 1,000,000,000$.

Output

For every test case output the answer multiply $2^n$ modulo $10^9 + 7$.

2
1
0 1
2
0 2
1 3

1
7

Hint

For the second sample, the excepted length is $\frac{0+2+2+3}{4}=\frac{7}{4}$.