Desiderium

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

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

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

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

BestCoder Round #57 (div.2)