#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, 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]}); nor.insert({i,mark[i]}); } else { if (nor.find({match[i],mark[i]}) == nor.end()) { cout << 0; return; } vector<pair<int,int>> rem; auto fix = hast.find({match[i],mark[i]}); fix++; if (fix != hast.end()) { G[mark[i]].push_back(fix->second); G[fix->second].push_back(mark[i]); badr[mark[i]] = 1; } for (auto it = nor.upper_bound({match[i],mark[i]});it != nor.end();it++) { auto it2 = hast.find(*it); int v = it->second; it2++; if (it2 != hast.end()) { if (badr[v]) { cout << 0; return; } G[v].push_back(it2->second); G[it2->second].push_back(v); rem.push_back(*it); } } for (auto val : rem) nor.erase(val); auto nxt = fix; fix--; if (nxt != hast.end() && fix != hast.begin()) { fix--; auto prev = fix; fix++; if (badr[prev->second]) { badr[prev->second] = 0; nor.erase(*prev); } else if (nor.find(*prev) == nor.end()) { badr[prev->second] = 1; nor.insert(*prev); } } else if (fix != hast.begin()) { fix--; badr[fix->second] = 0; nor.insert(*fix); } badr[mark[i]] = 0; hast.erase({match[i],mark[i]}); nor.erase({match[i],mark[i]}); } // cout << i << '\n'; // 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 << "badr : "; // for (int i = 1;i <= n;i++) { // cout << i << ',' << badr[i] << " "; // } // 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(); }