#include <cstdio> // Per scanf/printf
#include <vector>
#include <algorithm> // Per sort
#include <numeric> // Per fill
// Usiamo lo namespace std per brevità, come nell'originale
using namespace std;
// Definiamo un tipo per gli intervalli per chiarezza
using Interval = pair<int, int>;
// Costanti globali
const int LOG_MAX_COORD = 21; // Logaritmo della coordinata massima (2^21)
const int MAX_COORD = 1 << LOG_MAX_COORD; // Coordinata massima possibile
const int MOD = 1000000007;
// --- Classe Union-Find (Disjoint Set Union) per 2-SAT ---
// Gestisce i set disgiunti per tracciare i vincoli 2-SAT.
// Ogni variabile 'v' è rappresentata da due nodi:
// - v * 2 (rappresenta 'v è vero')
// - v * 2 + 1 (rappresenta 'v è falso')
class UnionFind
{
public:
// parent[i] = genitore del nodo i
// rank[i] = rango (profondità) dell'albero radicato in i
int parent[MAX_COORD * 2];
int rank[MAX_COORD * 2];
// Inizializza la struttura: ogni nodo è genitore di sé stesso
void init()
{
for (int i = 0; i < MAX_COORD * 2; i++)
{
parent[i] = i;
rank[i] = 0;
}
}
// Trova il rappresentante (radice) del set contenente 'a'
// Usa la "path compression" per efficienza
int find_set(int a)
{
if (a == parent[a])
return a;
else
return parent[a] = find_set(parent[a]);
}
// Unisce i due set che contengono 'a' e 'b'
// Usa "union by rank" per efficienza
void unite_sets(int a, int b)
{
a = find_set(a);
b = find_set(b);
if (a == b)
return; // Già uniti
if (rank[a] > rank[b])
{
parent[b] = a;
}
else
{
parent[a] = b;
}
if (rank[a] == rank[b])
rank[b]++;
}
};
// Istanza globale della struttura Union-Find
UnionFind uf;
// Aggiunge un vincolo 2-SAT tra due variabili (identificate dai loro tempi di inizio)
// 'start_time_1' e 'start_time_2' sono gli ID delle variabili.
void add_2sat_constraint(int start_time_1, int start_time_2, bool must_be_same)
{
// ID dei nodi 'true' e 'false' per la variabile 1
int v1_true = start_time_1 * 2;
int v1_false = start_time_1 * 2 + 1;
// ID dei nodi 'true' e 'false' per la variabile 2
int v2_true = start_time_2 * 2;
int v2_false = start_time_2 * 2 + 1;
if (must_be_same)
{
// Vincolo: v1 <-> v2 (devono avere lo stesso valore)
// Questo equivale a (v1 -> v2) AND (v2 -> v1)
// Che in 2-SAT si traduce in:
// (NOT v1 OR v2) -> unisci(v1_false, v2_true)
// (NOT v2 OR v1) -> unisci(v2_false, v1_true)
// Il codice originale unisce (v1_true, v2_true) e (v1_false, v2_false),
// che è un'implementazione equivalente e più diretta per l'implicazione <->
uf.unite_sets(v1_true, v2_true);
uf.unite_sets(v1_false, v2_false);
}
else
{
// Vincolo: v1 <-> NOT v2 (devono avere valori diversi)
// (v1 -> NOT v2) AND (NOT v2 -> v1)
// (NOT v1 OR NOT v2) -> unisci(v1_false, v2_false)
// (v2 OR v1) -> unisci(v2_true, v1_true)
// L'implementazione del codice originale è:
uf.unite_sets(v1_true, v2_false);
uf.unite_sets(v1_false, v2_true);
}
}
// --- Classe Segment Tree ---
// Questo non è un Segment Tree standard. È una struttura usata per
// decomporre gli intervalli e trovare efficientemente le sovrapposizioni.
class IntervalSegmentTree
{
public:
// Ogni nodo dell'albero contiene un vettore di intervalli
vector<Interval> node_intervals[1 << (LOG_MAX_COORD + 1)];
// Flag globale per tracciare se una soluzione è possibile
bool is_possible;
// Array temporanei usati in solve2/solve3 per evitare riallocazioni
int temp_idx[MAX_COORD];
int temp_imos[MAX_COORD]; // "IMOS" è una tecnica di programmazione dinamica/prefix sum
void init()
{
is_possible = true;
for (int i = 0; i < (1 << (LOG_MAX_COORD + 1)); i++)
node_intervals[i].clear();
}
// Aggiunge un intervallo [start, end] all'albero.
// L'intervallo viene inserito nel nodo più alto (più vicino alla radice)
// che "copre" l'intervallo, ma i cui figli non lo coprono completamente.
void add_interval_to_tree(int start, int end)
{
int node_idx = 1;
int lb = 0, ub = MAX_COORD - 1; // [lb, ub] è il range del nodo corrente
for (;;)
{
int mid = (lb + ub) / 2;
if (end <= mid)
{
// L'intervallo è tutto a sinistra
ub = mid;
node_idx = node_idx * 2;
}
else if (mid + 1 <= start)
{
// L'intervallo è tutto a destra
lb = mid + 1;
node_idx = node_idx * 2 + 1;
}
else
{
// L'intervallo scavalca il punto centrale (mid)
// Questo è il nodo corretto dove memorizzare l'intervallo
node_intervals[node_idx].push_back(make_pair(start, end));
break;
}
}
}
// --- Funzioni di Elaborazione dei Nodi ---
// Queste funzioni vengono chiamate durante la costruzione (calc())
// per aggiungere i vincoli 2-SAT in base alle sovrapposizioni.
// 1. process_node_internal_overlaps:
// Aggiunge vincoli per intervalli che si sovrappongono e che sono
// TUTTI memorizzati *direttamente* in questo nodo (node_intervals[node_idx]).
void process_node_internal_overlaps(int node_idx)
{
// Ordina gli intervalli per tempo di inizio
sort(node_intervals[node_idx].begin(), node_intervals[node_idx].end());
// 'dominant_intervals': intervalli "dominanti" (con fine decrescente)
// 'contained_intervals': intervalli "contenuti" (non dominanti)
vector<Interval> dominant_intervals, contained_intervals;
int min_end_so_far = 2e9; // Un numero grande
for (int i = 0; i < node_intervals[node_idx].size(); i++)
{
if (min_end_so_far > node_intervals[node_idx][i].second)
{
min_end_so_far = node_intervals[node_idx][i].second;
dominant_intervals.push_back(node_intervals[node_idx][i]);
}
else
{
contained_intervals.push_back(node_intervals[node_idx][i]);
}
}
// Controllo di coerenza: se tre intervalli si sovrappongono a catena
// in un modo particolare (A contiene B, B contiene C), può essere impossibile.
// Questo controlla se gli intervalli "contenuti" sono ordinati
// in modo non decrescente per 'end'. Se lo sono, c'è un conflitto.
for (int i = 1; i < contained_intervals.size(); i++)
{
if (contained_intervals[i - 1].second < contained_intervals[i].second)
is_possible = false;
}
// Aggiunge vincoli tra intervalli dominanti e contenuti che si sovrappongono
int pt = 0;
for (int i = 0; i < dominant_intervals.size(); i++)
{
for (;;)
{
if (pt == contained_intervals.size()) break;
// Se l'intervallo dominante 'i' si sovrappone al contenuto 'pt'
if (dominant_intervals[i].second > contained_intervals[pt].second) break;
if (dominant_intervals[i].first < contained_intervals[pt].first)
{
// Sovrapposizione trovata! Devono essere in gruppi diversi.
add_2sat_constraint(dominant_intervals[i].first, contained_intervals[pt].first, false);
}
pt++;
}
if (pt != 0) pt--;
}
}
// 2. process_left_child_overlaps:
// Aggiunge vincoli tra gli intervalli del *figlio sinistro* (node_idx * 2)
// e gli intervalli di *questo nodo* (node_idx).
void process_left_child_overlaps(int node_idx, int lb, int ub)
{
// [lb, ub] è il range del figlio sinistro
int node_range_len = ub - lb + 1;
fill(temp_idx, temp_idx + node_range_len, -1);
fill(temp_imos, temp_imos + node_intervals[node_idx].size() + 1, 0);
// Mappa le coordinate 'start' agli indici del vettore node_intervals[node_idx]
for (int i = 0; i < node_intervals[node_idx].size(); i++)
temp_idx[node_intervals[node_idx][i].first - lb] = i;
for (int i = 1; i < node_range_len; i++)
if (temp_idx[i] == -1) temp_idx[i] = temp_idx[i - 1];
// Per ogni intervallo nel figlio sinistro...
for (int i = 0; i < node_intervals[node_idx * 2].size(); i++)
{
Interval child_interval = node_intervals[node_idx * 2][i];
int start_idx = temp_idx[child_interval.first - lb];
int end_idx = temp_idx[child_interval.second - lb];
if (start_idx < end_idx)
{
// L'intervallo del figlio [start, end] si sovrappone a un
// range di intervalli [start_idx, end_idx] in questo nodo.
// Usa la tecnica IMOS (array delle differenze) per marcare il range.
temp_imos[start_idx + 1]++;
temp_imos[end_idx]--;
// Aggiunge vincolo tra l'intervallo figlio e l'intervallo 'end_idx'
// (l'ultimo intervallo del nodo padre con cui si sovrappone)
add_2sat_constraint(child_interval.first, node_intervals[node_idx][end_idx].first, false);
}
}
// Calcola la somma prefissa (prefix sum) dell'array IMOS
for (int i = 1; i <= node_intervals[node_idx].size(); i++)
temp_imos[i] += temp_imos[i - 1];
// Se imos[i] > 0, significa che l'intervallo 'i' di questo nodo
// è sovrapposto da *almeno un* intervallo del figlio sinistro.
// Se imos[i] > 0, allora gli intervalli 'i' e 'i+1' di questo nodo
// devono essere messi *nello stesso gruppo* (true).
for (int i = 0; i < int(node_intervals[node_idx].size()) - 1; i++)
if (temp_imos[i] > 0)
add_2sat_constraint(node_intervals[node_idx][i].first, node_intervals[node_idx][i + 1].first, true);
}
// 3. process_right_child_overlaps:
// Simmetrico a process_left_child_overlaps, ma per il *figlio destro*.
// Usa un trucco di ordinamento (swap/sort/swap) per ordinare per 'end'
// e riutilizzare la stessa logica.
void process_right_child_overlaps(int node_idx, int lb, int ub)
{
// [lb, ub] è il range del figlio destro
// Ordina per 'end'
for (int i = 0; i < node_intervals[node_idx].size(); i++)
swap(node_intervals[node_idx][i].first, node_intervals[node_idx][i].second);
sort(node_intervals[node_idx].begin(), node_intervals[node_idx].end());
for (int i = 0; i < node_intervals[node_idx].size(); i++)
swap(node_intervals[node_idx][i].first, node_intervals[node_idx][i].second);
// La logica è identica a 'process_left_child_overlaps',
// ma ora 'temp_idx' mappa le coordinate 'end'
int node_range_len = ub - lb + 1;
fill(temp_idx, temp_idx + node_range_len, -1);
fill(temp_imos, temp_imos + node_intervals[node_idx].size() + 1, 0);
for (int i = 0; i < node_intervals[node_idx].size(); i++)
temp_idx[node_intervals[node_idx][i].second - lb] = i;
for (int i = 1; i < node_range_len; i++)
if (temp_idx[i] == -1) temp_idx[i] = temp_idx[i - 1];
for (int i = 0; i < node_intervals[node_idx * 2 + 1].size(); i++)
{
Interval child_interval = node_intervals[node_idx * 2 + 1][i];
int start_idx = temp_idx[child_interval.first - lb];
int end_idx = temp_idx[child_interval.second - lb];
if (start_idx < end_idx)
{
temp_imos[start_idx + 1]++;
temp_imos[end_idx]--;
add_2sat_constraint(child_interval.first, node_intervals[node_idx][end_idx].first, false);
}
}
for (int i = 1; i <= node_intervals[node_idx].size(); i++)
temp_imos[i] += temp_imos[i - 1];
for (int i = 0; i < int(node_intervals[node_idx].size()) - 1; i++)
if (temp_imos[i] > 0)
add_2sat_constraint(node_intervals[node_idx][i].first, node_intervals[node_idx][i + 1].first, true);
}
// Funzione principale che costruisce l'albero e tutti i vincoli
// Procede "bottom-up", dalle foglie (livello LOG-1) alla radice (livello 0)
void build_constraints()
{
for (int level = LOG_MAX_COORD - 1; level >= 0; level--)
{
for (int j = 0; j < (1 << level); j++)
{
int node_idx = (1 << level) + j;
int node_lb = j << (LOG_MAX_COORD - level);
int node_ub = ((j + 1) << (LOG_MAX_COORD - level)) - 1;
int node_mid = node_lb + (1 << (LOG_MAX_COORD - 1 - level)) - 1;
// 1. Processa sovrapposizioni interne al nodo
process_node_internal_overlaps(node_idx);
// 2. Processa sovrapposizioni tra figlio sx e nodo
process_left_child_overlaps(node_idx, node_lb, node_mid);
// 3. Processa sovrapposizioni tra figlio dx e nodo
process_right_child_overlaps(node_idx, node_mid + 1, node_ub);
// "Sposta" (copia) gli intervalli dai figli a questo nodo
// per l'elaborazione al livello superiore
for (int k = 0; k < node_intervals[node_idx * 2].size(); k++)
node_intervals[node_idx].push_back(node_intervals[node_idx * 2][k]);
for (int k = 0; k < node_intervals[node_idx * 2 + 1].size(); k++)
node_intervals[node_idx].push_back(node_intervals[node_idx * 2 + 1][k]);
}
}
}
};
// --- Funzione Main ---
int main()
{
int num_intervals;
scanf("%d", &num_intervals);
IntervalSegmentTree tree;
tree.init();
uf.init();
vector<Interval> input_intervals;
for (int i = 0; i < num_intervals; i++)
{
int start, end;
scanf("%d%d", &start, &end);
start--, end--; // 0-indexa le coordinate
input_intervals.push_back(make_pair(start, end));
tree.add_interval_to_tree(start, end);
}
// Costruisce la struttura e aggiunge tutti i vincoli 2-SAT
tree.build_constraints();
// --- Controllo Finale e Calcolo della Risposta ---
// 1. Controlla se c'è una contraddizione (v <-> NOT v)
// Se per qualsiasi variabile 'v', 'v' e 'NOT v' sono nello stesso set,
// allora è impossibile.
for (int i = 0; i < num_intervals; i++)
{
int start_time = input_intervals[i].first;
if (uf.find_set(start_time * 2) == uf.find_set(start_time * 2 + 1))
{
tree.is_possible = false;
}
}
// 2. Conta le componenti connesse
// Se la soluzione è valida, il numero di modi per assegnare le gru
// è 2 elevato al numero di "scelte indipendenti".
// Contiamo il numero di radici (rappresentanti) nel DSU
// tra tutte le variabili (v_true e v_false).
int num_components = 0;
for (int i = 0; i < num_intervals; i++)
{
int start_time = input_intervals[i].first;
// Controlla il nodo 'true'
if (uf.find_set(start_time * 2) == start_time * 2)
num_components++;
// Controlla il nodo 'false'
if (uf.find_set(start_time * 2 + 1) == start_time * 2 + 1)
num_components++;
}
// Se non è possibile, 'ans' è 0
// Altrimenti, 'ans' è 1
long long ans = tree.is_possible ? 1 : 0;
// Il numero di scelte indipendenti è num_components / 2
// Calcoliamo (ans * 2^(num_components / 2)) % MOD
for (int i = 0; i < num_components / 2; i++)
{
ans = (ans * 2) % MOD;
}
printf("%lld\n", ans);
return 0;
}
