Counting Tree Subsets in Interval Graph

We are given a social circle with ( n ) people. Person ( i ) has an interval of SAN values ( [l_i, r_i] ). Two people have a PY relationship if their intervals intersect (i.e. their intersection is non‐empty).

Now, choose a nonempty set ( S ) of people such that if we connect every pair of people in ( S ) that have a PY relationship by an edge, the resulting graph is a tree (i.e. it must be connected and have exactly ( |S| - 1 ) edges – a forest is not allowed). Note that a single vertex is considered a tree.

Your task is to count the number of ways to choose such a set ( S ). Since the answer might be huge, output it modulo ( 10^9+7 ).

inputFormat

The first line contains an integer ( n ) (the number of people). Each of the following ( n ) lines contains two integers ( l_i ) and ( r_i ) representing the SAN interval of person ( i ).

outputFormat

Output a single integer, the number of valid subsets ( S ) modulo ( 10^9+7 ).

sample

3
1 2
2 3
3 4

6