#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<pair<int,int>> G[N]; int is[N]; void DFS(int v) { for (auto u : G[v]) { if (!is[u.first]) { is[u.first] = (is[v]+u.second*is[v])%3; DFS(u.first); } else if (is[u.first] != ((is[v]+u.second*is[v])%3)) { cout << 0; exit(0); } } } 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,1}); G[fix->second].push_back({mark[i],1}); 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,0}); G[it2->second].push_back({v,0}); 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'; } // for (int i = 1;i <= n;i++) { // cout << i << " : "; // for (auto u : G[i]) { // cout << u.first << ' ' << u.second << " - "; // } // cout << '\n'; // } int c = 0; for (int i = 1;i <= n;i++) { if (!is[i]) { is[i] = 1; 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(); }