#include<iostream> #include<vector> #include<algorithm> #include<set> using namespace std; #define ll long long #define ld long double #define pii pair<int, int> #define pli pair<ll, ll> #define ppi pair<pii, pii> #define RUN_LIKE_DJAWAD (ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0)); #define DECIMAL_OUTPUT cout << fixed << setprecision(9); #define pb push_back #define pf push_top #define ff first #define ss second #define maxn 2000001 int seg[maxn << 2]; vector<int> now; set<int> av[maxn]; int col[maxn]; int st[maxn], fn[maxn]; int sz[maxn], par[maxn]; vector<int> g[maxn]; int n; void upd(int l, int r, int p, int x, int id){ if (l == r){ seg[id] = x; return; } int mid = (l + r) >> 1; if (p <= mid) upd(l, mid, p, x, id << 1); else upd(mid + 1, r, p, x, (id << 1) + 1); seg[id] = seg[id << 1] + seg[(id << 1) + 1]; } int get(int v){ while (par[v] != -1) v = par[v]; return v; } void merge(int u, int v){ int pu = get(u), pv = get(v); if (pu != pv){ g[u].pb(v); g[v].pb(u); if (sz[pu] < sz[pv]) swap(pu, pv); if (not av[pu].empty()) upd(1, n << 1, *av[pu].begin(), 0, 1); if (not av[pv].empty()) upd(1, n << 1, *av[pv].begin(), 0, 1); for (int p: av[pv]) av[pu].insert(p); av[pv].clear(); if (not av[pu].empty()) upd(1, n << 1, *av[pu].begin(), 1, 1); par[pv] = pu; sz[pu] += sz[pv]; } } void gbv(int l, int r, int s, int e, int id){ if (seg[id] == 0 or s > r or e < l) return; if (l == r){ now.pb(col[l]); return; } int mid = (l + r) >> 1; gbv(l, mid, s, e, id << 1); gbv(mid + 1, r, s, e, (id << 1) + 1); } bool seen[maxn]; int cl[maxn]; void dfs(int v, int nc){ seen[v] = true; cl[v] = nc; for (int u: g[v]) if (not seen[u]) dfs(u, nc ^ 1); } int gs(int l, int r, int s, int e, int id){ if (s > r or e < l) return 0; if (s <= l and e >= r) return seg[id]; int mid = (l + r) >> 1; return gs(l, mid, s, e, id << 1) + gs(mid + 1, r, s, e, (id << 1) + 1); } const int mod = 1e9 + 7; int main(){ RUN_LIKE_DJAWAD cin >> n; for (int i = 1; i <= n; i++){ cin >> st[i] >> fn[i]; col[st[i]] = i, col[fn[i]] = i; } for (int i = 1; i <= n; i++) par[i] = -1, sz[i] = 1; for (int i = 1; i <= n << 1; i++){ int c = col[i]; int s = st[c], e = fn[c]; int ncc = get(c); if (not av[ncc].empty()) upd(1, n << 1, *av[ncc].begin(), 0, 1); if (s == i){ av[ncc].insert(e); upd(1, n << 1, *av[ncc].begin(), 1, 1); gbv(1, n << 1, s + 1, e - 1, 1); for (int u: now) merge(c, u); now.clear(); } else { av[ncc].erase(e); if (not av[ncc].empty()) upd(1, n << 1, *av[ncc].begin(), 1, 1); } } int ans = 1; for (int i = 1; i <= n; i++) if (not seen[i]){ ans = (ans << 1) % mod; dfs(i, 1); } for (int i = 1; i < maxn << 2; i++) seg[i] = 0; for (int i = 1; i <= n << 1; i++){ int c = col[i]; int s = st[c], e = fn[c]; if (s == i){ if (cl[c] == 0){ upd(1, n << 1, e, 1, 1); if (gs(1, n << 1, s + 1, e - 1, 1) > 0) ans = 0; } } else { if (cl[c] == 0) upd(1, n << 1, e, 0, 1); } } for (int i = 1; i < maxn << 2; i++) seg[i] = 0; for (int i = 1; i <= n << 1; i++){ int c = col[i]; int s = st[c], e = fn[c]; if (s == i){ if (cl[c] == 1){ upd(1, n << 1, e, 1, 1); if (gs(1, n << 1, s + 1, e - 1, 1) > 0) ans = 0; } } else { if (cl[c] == 1) upd(1, n << 1, e, 0, 1); } } // for (int i = 1; i <= n; i++) cout << cl[i] << " "; // cout << "\n"; cout << ans << "\n"; }