#include<bits/stdc++.h> using namespace std; #define int long long const int N = 1e6+6, MOD = 1e9+7; int n; pair<int,int> nums[N]; int mark[2*N], match[2*N]; bool badr[N]; set<pair<int,int>> hast, nol, nor; vector<int> G[N]; bool is[N]; void DFS(int v) { is[v] = 1; for (int u : G[v]) { if (!is[u]) { DFS(u); } } } void solve() { cin >> n; for (int i = 1;i <= n;i++) { cin >> nums[i].first >> nums[i].second; mark[nums[i].first] = i; mark[nums[i].second] = i; match[nums[i].first] = nums[i].second; match[nums[i].second] = nums[i].first; } for (int i = 1;i <= 2*n;i++) { if (match[i] > i) { hast.insert({i,mark[i]}); nol.insert({i,mark[i]}); nor.insert({i,mark[i]}); } else { if (nor.find({match[i],mark[i]}) == nor.end()) { cout << 0; return; } vector<pair<int,int>> rem; for (auto it = nor.lower_bound({match[i],mark[i]});it != nor.end();it++) { auto it2 = hast.find(*it); int v = it2->second; if (badr[v] && v != mark[i]) { cout << 0; return; } it2++; if (it2 != hast.end()) { G[v].push_back(it2->second); rem.push_back(*it); } } for (auto val : rem) nor.erase(val); rem.clear(); for (auto it = nol.upper_bound({match[i],mark[i]});it != nol.end();it++) { auto it2 = hast.find(*it); int v = it2->second; if (it2 != hast.begin()) { it2--; G[v].push_back(it2->second); rem.push_back(*it); } } for (auto val : rem) { nol.erase(val); } rem.clear(); auto it = hast.find({match[i],mark[i]}); if (nol.find({match[i],mark[i]}) == nol.end()) { it--; badr[it->second] = 1; it++; } it++; if (it != hast.end()) { nol.insert(*it); } it--; if (it != hast.begin()) { it--; nor.insert(*it); } nol.erase({match[i],mark[i]}); nor.erase({match[i],mark[i]}); hast.erase({match[i],mark[i]}); } // cout << i << endl; // cout << "hast : "; // for (auto val : hast) { // cout << val.first << ' ' << val.second << " - "; // } // cout << '\n'; // cout << "nor : "; // for (auto val : nor) { // cout << val.first << ' ' << val.second << " - "; // } // cout << '\n'; // cout << "nol : "; // for (auto val : nol) { // cout << val.first << ' ' << val.second << " - "; // } // cout << '\n'; } int c = 0; for (int i = 1;i <= n;i++) { if (!is[i]) { DFS(i); c++; } } int ans = 1; for (int i = 0;i < c;i++) { ans = (ans*2)%MOD; } cout << ans; } int32_t main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); solve(); }