#include <bits/stdc++.h> using namespace std; #define FOR(i, a, b) for(int i = a; i <= b; i++) #define FOD(i, a, b) for(int i = a; i >= b; i--) #define fi first #define se second #define ll long long #define db double #define ii pair<int,int> #define pb push_back #define MASK(i) (1LL << i) #define sq(i) (1LL * (i) * (i)) #define task "task" const ll INF = 1e18; const int inf = 1e9; const int N = 1e6 + 4; const int mod = 1e9 + 7; int n, res = 1; ii a[N]; int idx[2 * N], c[N], cnt[2], save[N][2]; struct SmtMax { int mx[8 * N]; void init() { FOR(i, 1, 8 * n) mx[i] = -1; } void upd(int id, int l, int r, int pos, int d) { assert(l <= r); if(l == r) { mx[id] = d; return; } int mid = l + r >> 1; if(pos <= mid) upd(id << 1, l, mid, pos, d); else upd(id << 1 | 1, mid + 1, r, pos, d); mx[id] = max(mx[id << 1], mx[id << 1 | 1]); } int get(int id, int l, int r, int u, int v) { if(l > v || r < u || u > v) return -1; if(l >= u && r <= v) return mx[id]; int mid = l + r >> 1; return max(get(id << 1, l, mid, u, v), get(id << 1 | 1, mid + 1, r, u, v)); } } smtmax; struct SmtMin { int mn[8 * N]; void init() { FOR(i, 1, 8 * n) mn[i] = 2 * n + 1; } void upd(int id, int l, int r, int pos, int d) { assert(l <= r); if(l == r) { mn[id] = d; return; } int mid = l + r >> 1; if(pos <= mid) upd(id << 1, l, mid, pos, d); else upd(id << 1 | 1, mid + 1, r, pos, d); mn[id] = min(mn[id << 1], mn[id << 1 | 1]); } int get(int id, int l, int r, int u, int v) { if(l > v || r < u || u > v) return 2 * n + 1; if(l >= u && r <= v) return mn[id]; int mid = l + r >> 1; return min(get(id << 1, l, mid, u, v), get(id << 1 | 1, mid + 1, r, u, v)); } } smtmin; void dfs(int u, int col) { c[u] = col; smtmax.upd(1, 1, 2 * n, a[u].fi, -1); smtmin.upd(1, 1, 2 * n, a[u].se, 2 * n + 1); while(true) { int p = smtmax.get(1, 1, 2 * n, a[u].fi + 1, a[u].se - 1); if(p <= a[u].se) break; dfs(idx[p], col ^ 1); } while(true) { int p = smtmin.get(1, 1, 2 * n, a[u].fi + 1, a[u].se - 1); if(p >= a[u].fi) break; dfs(idx[p], col ^ 1); } } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n; FOR(i, 1, n) { cin >> a[i].fi >> a[i].se; idx[a[i].fi] = i; idx[a[i].se] = i; } smtmax.init(); smtmin.init(); FOR(i, 1, n) { smtmax.upd(1, 1, 2 * n, a[i].fi, a[i].se); smtmin.upd(1, 1, 2 * n, a[i].se, a[i].fi); c[i] = -1; } FOR(i, 1, n) if(c[i] == -1) { dfs(i, 0); (res *= 2) %= mod; } vector<ii> ev; FOR(i, 1, n) { save[i][0] = save[i][1] = -1; ev.pb({a[i].fi, i}); ev.pb({a[i].se, i}); } sort(ev.begin(), ev.end()); for(ii x : ev) { int p = x.fi; int id = x.se; if(save[id][0] == -1) { save[id][0] = cnt[0]; save[id][1] = cnt[1]; cnt[c[id]]++; } else { if(cnt[c[id]] - save[id][c[id]] > 1) { cout << 0 << '\n'; return 0; } cnt[c[id]]--; } } cout << res << '\n'; }