#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int, int> pii;
#define SEGTREE_SIZE (1 << 21)
#define LOG 21
class UnionFind {
public:
int parent[SEGTREE_SIZE * 2];
int rank[SEGTREE_SIZE * 2];
void init() {
for (int i = 0; i < SEGTREE_SIZE * 2; i++) {
parent[i] = i;
rank[i] = 0;
}
}
int find(int x) {
if (x == parent[x]) return x;
return parent[x] = find(parent[x]);
}
void unite(int x, int y) {
x = find(x);
y = find(y);
if (x == y) return;
if (rank[x] > rank[y]) {
parent[y] = x;
} else {
parent[x] = y;
if (rank[x] == rank[y]) rank[y]++;
}
}
};
UnionFind uf;
// Aggiunge un vincolo tra due intervalli
void add_constraint(int interval_a, int interval_b, bool same_stack) {
// Ogni intervallo ha due possibili posizioni:
// interval*2 = stack1, interval*2+1 = stack2
if (same_stack) {
// Stesso stack: (a0 <-> b0) e (a1 <-> b1)
uf.unite(interval_a * 2, interval_b * 2);
uf.unite(interval_a * 2 + 1, interval_b * 2 + 1);
} else {
// Stack diversi: (a0 <-> b1) e (a1 <-> b0)
uf.unite(interval_a * 2, interval_b * 2 + 1);
uf.unite(interval_a * 2 + 1, interval_b * 2);
}
}
class IntervalSolver {
public:
vector<pii> node_segments[1 << (LOG + 1)]; // Segmenti in ogni nodo
bool is_valid; // Se la soluzione è possibile
void init() {
is_valid = true;
for (int i = 0; i < (1 << (LOG + 1)); i++) {
node_segments[i].clear();
}
}
// Aggiunge un intervallo al segment tree
void add_interval(int start, int end) {
int node = 1;
int left = 0, right = (1 << LOG) - 1;
while (true) {
int mid = (left + right) / 2;
if (end <= mid) {
// Intervallo completamente a sinistra
right = mid;
node = node * 2;
} else if (start >= mid + 1) {
// Intervallo completamente a destra
left = mid + 1;
node = node * 2 + 1;
} else {
// Intervallo centrale (attraversa mid)
node_segments[node].push_back(make_pair(start, end));
break;
}
}
}
// Risolve i conflitti tra intervalli dello stesso nodo
void solve_node_conflicts(int node, int left_bound, int right_bound) {
if (node_segments[node].empty()) return;
// Ordina gli intervalli per start point
sort(node_segments[node].begin(), node_segments[node].end());
vector<pii> non_nested, nested;
int min_end = 1000000000;
// Separa in non annidati e annidati
for (int i = 0; i < node_segments[node].size(); i++) {
if (node_segments[node][i].second < min_end) {
min_end = node_segments[node][i].second;
non_nested.push_back(node_segments[node][i]);
} else {
nested.push_back(node_segments[node][i]);
}
}
// Verifica che gli intervalli annidati siano in ordine decrescente di end
for (int i = 1; i < nested.size(); i++) {
if (nested[i - 1].second < nested[i].second) {
is_valid = false;
return;
}
}
// Aggiungi vincoli tra non_nested e nested
int ptr = 0;
for (int i = 0; i < non_nested.size(); i++) {
while (ptr < nested.size() && nested[ptr].second < non_nested[i].second) {
// Conflitto: devono avere stack diversi
add_constraint(non_nested[i].first, nested[ptr].first, false);
ptr++;
}
if (ptr > 0) ptr--;
}
}
int temp_index[SEGTREE_SIZE];
int prefix_sum[SEGTREE_SIZE];
// Risolve conflitti tra nodo corrente e figlio sinistro
void solve_left_child_conflicts(int node, int left_bound, int right_bound) {
if (node_segments[node].empty() || node_segments[node * 2].empty()) return;
int mid = (left_bound + right_bound) / 2;
int left_size = mid - left_bound + 1;
// Inizializza array temporanei
fill(temp_index, temp_index + left_size, -1);
fill(prefix_sum, prefix_sum + node_segments[node].size() + 1, 0);
// Costruisci indice per mapping veloce
for (int i = 0; i < node_segments[node].size(); i++) {
int pos = node_segments[node][i].first - left_bound;
if (pos < left_size) {
temp_index[pos] = i;
}
}
for (int i = 1; i < left_size; i++) {
if (temp_index[i] == -1) {
temp_index[i] = temp_index[i - 1];
}
}
// Processa intervalli del figlio sinistro
for (int i = 0; i < node_segments[node * 2].size(); i++) {
int start_idx = node_segments[node * 2][i].first - left_bound;
int end_idx = node_segments[node * 2][i].second - left_bound;
if (start_idx < left_size && end_idx < left_size &&
temp_index[start_idx] != -1 && temp_index[end_idx] != -1 &&
temp_index[start_idx] < temp_index[end_idx]) {
prefix_sum[temp_index[start_idx] + 1]++;
prefix_sum[temp_index[end_idx]]--;
}
}
// Aggiungi vincoli per conflitti diretti
for (int i = 0; i < node_segments[node * 2].size(); i++) {
int start_idx = node_segments[node * 2][i].first - left_bound;
int end_idx = node_segments[node * 2][i].second - left_bound;
if (start_idx < left_size && end_idx < left_size &&
temp_index[start_idx] != -1 && temp_index[end_idx] != -1 &&
temp_index[start_idx] < temp_index[end_idx]) {
add_constraint(node_segments[node * 2][i].first,
node_segments[node][temp_index[end_idx]].first, false);
}
}
// Calcola prefix sum e aggiungi vincoli tra intervalli consecutivi
for (int i = 1; i <= node_segments[node].size(); i++) {
prefix_sum[i] += prefix_sum[i - 1];
}
for (int i = 0; i < (int)node_segments[node].size() - 1; i++) {
if (prefix_sum[i] > 0) {
add_constraint(node_segments[node][i].first,
node_segments[node][i + 1].first, true);
}
}
}
// Risolve conflitti tra nodo corrente e figlio destro (simmetrico)
void solve_right_child_conflicts(int node, int left_bound, int right_bound) {
if (node_segments[node].empty() || node_segments[node * 2 + 1].empty()) return;
int mid = (left_bound + right_bound) / 2;
int right_start = mid + 1;
int right_size = right_bound - right_start + 1;
// Ordina gli intervalli per end point
vector<pii> sorted_by_end = node_segments[node];
for (int i = 0; i < sorted_by_end.size(); i++) {
swap(sorted_by_end[i].first, sorted_by_end[i].second);
}
sort(sorted_by_end.begin(), sorted_by_end.end());
for (int i = 0; i < sorted_by_end.size(); i++) {
swap(sorted_by_end[i].first, sorted_by_end[i].second);
}
// Inizializza array temporanei
fill(temp_index, temp_index + right_size, -1);
fill(prefix_sum, prefix_sum + node_segments[node].size() + 1, 0);
// Costruisci indice per end point
for (int i = 0; i < sorted_by_end.size(); i++) {
int pos = sorted_by_end[i].second - right_start;
if (pos < right_size) {
temp_index[pos] = i;
}
}
for (int i = 1; i < right_size; i++) {
if (temp_index[i] == -1) {
temp_index[i] = temp_index[i - 1];
}
}
// Processa intervalli del figlio destro
for (int i = 0; i < node_segments[node * 2 + 1].size(); i++) {
int start_idx = node_segments[node * 2 + 1][i].first - right_start;
int end_idx = node_segments[node * 2 + 1][i].second - right_start;
if (start_idx < right_size && end_idx < right_size &&
temp_index[start_idx] != -1 && temp_index[end_idx] != -1 &&
temp_index[start_idx] < temp_index[end_idx]) {
prefix_sum[temp_index[start_idx] + 1]++;
prefix_sum[temp_index[end_idx]]--;
}
}
// Aggiungi vincoli per conflitti diretti
for (int i = 0; i < node_segments[node * 2 + 1].size(); i++) {
int start_idx = node_segments[node * 2 + 1][i].first - right_start;
int end_idx = node_segments[node * 2 + 1][i].second - right_start;
if (start_idx < right_size && end_idx < right_size &&
temp_index[start_idx] != -1 && temp_index[end_idx] != -1 &&
temp_index[start_idx] < temp_index[end_idx]) {
add_constraint(node_segments[node * 2 + 1][i].first,
sorted_by_end[temp_index[end_idx]].first, false);
}
}
// Calcola prefix sum e aggiungi vincoli tra intervalli consecutivi
for (int i = 1; i <= sorted_by_end.size(); i++) {
prefix_sum[i] += prefix_sum[i - 1];
}
for (int i = 0; i < (int)sorted_by_end.size() - 1; i++) {
if (prefix_sum[i] > 0) {
add_constraint(sorted_by_end[i].first, sorted_by_end[i + 1].first, true);
}
}
}
// Calcola la soluzione con divide and conquer
void solve() {
for (int level = LOG - 1; level >= 0; level--) {
for (int node_idx = 0; node_idx < (1 << level); node_idx++) {
int node = (1 << level) + node_idx;
int segment_start = node_idx << (LOG - level);
int segment_end = ((node_idx + 1) << (LOG - level)) - 1;
if (!is_valid) return;
solve_node_conflicts(node, segment_start, segment_end);
solve_left_child_conflicts(node, segment_start, segment_end);
solve_right_child_conflicts(node, segment_start, segment_end);
// Merge degli intervalli dai figli
for (int i = 0; i < node_segments[node * 2].size(); i++) {
node_segments[node].push_back(node_segments[node * 2][i]);
}
for (int i = 0; i < node_segments[node * 2 + 1].size(); i++) {
node_segments[node].push_back(node_segments[node * 2 + 1][i]);
}
}
}
}
};
IntervalSolver solver;
int main() {
int num_intervals;
scanf("%d", &num_intervals);
solver.init();
vector<pii> intervals;
// Lettura input
for (int i = 0; i < num_intervals; i++) {
int start, end;
scanf("%d%d", &start, &end);
start--; end--;
intervals.push_back(make_pair(start, end));
solver.add_interval(start, end);
}
uf.init();
solver.solve();
// Verifica consistenza
for (int i = 0; i < num_intervals; i++) {
if (uf.find(intervals[i].first * 2) == uf.find(intervals[i].first * 2 + 1)) {
solver.is_valid = false;
break;
}
}
if (!solver.is_valid) {
printf("0\n");
return 0;
}
// Conta componenti connesse
int component_count = 0;
for (int i = 0; i < num_intervals; i++) {
if (uf.find(intervals[i].first * 2) == intervals[i].first * 2) {
component_count++;
}
if (uf.find(intervals[i].first * 2 + 1) == intervals[i].first * 2 + 1) {
component_count++;
}
}
int result = 1;
int mod = 1000000007;
for (int i = 0; i < component_count / 2; i++) {
result = (result * 2) % mod;
}
printf("%d\n", result);
return 0;
}
