#include <bits/stdc++.h>
/*
Entre tanta gente yo te vi llegar
Algo en el destino me hizo saludar
Te dije me nombre e no sé dónde
Como con un beso me respondes
*/
#define debug printf
#define all(x) x.begin(),x.end()
#define sz(x) (int)(x.size())
#define ll long long
const int MAX = 2e6+10 ;
const int MOD = 1e9+7 ;
using namespace std ;
int N ;
int L[MAX] , R[MAX] ;
int saveL[MAX], saveR[MAX] ;
int beginsHere[MAX], endsHere[MAX] ;
struct Seg
{
//Seg zero means I'm searching i s.t. L[i] < L
int type ;
int tree[MAX*4] ;
int m(int l, int r ) { return (l+r)>>1 ; }
int merge(int type , int lef, int rig)
{
if( !type ) return ( L[lef ]< L[rig] ) ? lef : rig ;
return (R[lef] >R[rig] ) ? lef : rig ;
}
void build(int pos, int l, int r )
{
if( l == r )
{
tree[pos] = type ? beginsHere[l] : endsHere[r] ;
return ;
}
build(pos<<1 , l , m(l,r) ) ;
build(pos<<1|1 , m(l,r)+1, r ) ;
tree[pos] = merge(type, tree[pos<<1], tree[pos<<1|1] ) ;
}
void makeRemoval(int pos, int l, int r, int x )
{
if( l == r ) return ;
if( x <= m(l,r) ) makeRemoval(pos<<1 , l , m(l,r) , x ) ;
else makeRemoval(pos<<1|1 , m(l,r)+1, r, x ) ;
tree[pos] = merge(type, tree[pos<<1], tree[pos<<1|1] ) ;
}
int qry(int pos, int l, int r, int beg, int en )
{
// debug("%d %d and look for %d %d and ans %d\n", l, r, beg, en, tree[pos] ) ;
if( l > en || r < beg ) return 0 ;
if( l >= beg && r <= en ) return tree[pos] ;
int al = qry(pos<<1 , l , m(l,r) , beg, en ) ;
int ar = qry(pos<<1|1 , m(l,r)+1, r, beg, en ) ;
return merge(type, al, ar ) ;
}
} seg[2] ;
int main()
{
seg[0].type = 0 ;
seg[1].type = 1 ;
scanf("%d", &N ) ;
for(int i= 1 ; i <= N ; i++ )
{
scanf("%d %d", &L[i] , &R[i] ) ;
saveL[i] = L[i] ; saveR[i] = R[i] ;
beginsHere[ L[i] ] = i ;
endsHere[ R[i] ] = i ;
}
L[0] = 2*N+1 ;
R[0] = -1 ;
seg[0].build(1,1,2*N) ;
seg[1].build(1,1,2*N) ;
vector<int> color(N+1,-1) ;
color[0] = 0 ;
int ans= 1 ;
for(int i= 1 ; i <= N ; i++ )
{
if( color[i] != -1 ) continue ;
ans <<= 1 ;
if(ans >= MOD ) ans -= MOD ;
vector<int> fila(1,i) ;
color[i] = 0 ;
int ini = 0 ;
L[i] = 2*N+1 ;
R[i] = -1 ;
seg[0].makeRemoval(1,1,2*N, saveR[i] ) ;
seg[1].makeRemoval(1,1,2*N, saveL[i] ) ;
while( ini < sz(fila) )
{
int x = fila[ini++] ;
int y;
for(int j = 0 ; j < 2 ; j++ )
{
y = seg[j].qry(1,1,2*N, saveL[x] , saveR[x] ) ;
while( color[y] == -1 && ( (!j && L[y] < saveL[x]) || (j && R[y] > saveR[x] ) ) )
{
color[y] = !color[x] ;
L[y] = 2*N+1 ;
R[y] = -1 ;
seg[0].makeRemoval(1,1,2*N, saveR[y] ) ;
seg[1].makeRemoval(1,1,2*N, saveL[y] ) ;
fila.push_back(y) ;
y = seg[j].qry( 1, 1, 2*N, saveL[x], saveR[x] ) ;
}
}
}
}
vector<int> toSort(N) ; iota(all(toSort),1) ;
sort( all(toSort), [&](int i, int j) { return saveL[i] < saveL[j] ; } ) ;
set<int> s[2] ;
for(auto e : toSort )
{
int c = color[e] ;
auto it = s[c].upper_bound(saveR[e]) ;
if(it != s[c].begin() )
{
it-- ;
if( *it > saveL[e] )
{
printf("0\n" ) ;
return 0 ;
}
}
s[c].insert(saveR[e] ) ;
}
printf("%d\n", ans ) ;
}
