1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#define ll unsigned long long
using namespace std;

int base = 1;
void update(int l, int r, int x, vector <int> &drzewo){
    l += base - 1;
    r += base + 1;
    while (l/2 != r/2){
        if (l % 2 == 0){
            drzewo[l+1] = x;
        }
        if (r % 2 == 1){
            drzewo[r-1] = x;
        }
        l /= 2;
        r /= 2;
    }
}

int query (int v, vector <int> &drzewo){
    v += base;
    int wynik = drzewo[v];
    while (v > 1){
        v /= 2;
        wynik = max(wynik, drzewo[v]);
    }
    return wynik;
}

ll NWD(ll a, ll b){
    if(b == 0) return a;
    return NWD(b, a%b);
}

pair <ll, ll> dodawanie(pair <ll, ll> a, pair <ll, ll> b){
    ll mianownik = (a.second*b.second)/NWD(a.second, b.second);
    ll licznik = a.first*(mianownik/a.second) + b.first*(mianownik/b.second);
    ll dzielnik = NWD(licznik, mianownik);
    return {licznik/dzielnik, mianownik/dzielnik};
}

ll szybkie_potegowanie(ll a, ll b, ll mod){
    ll wynik = 1;
    a = a % mod;
    while (b > 0){
        if (b % 2 == 1){
            wynik = (wynik * a) % mod;
        }
        a = (a * a) % mod;
        b /= 2;
    }
    return wynik;
}

ll odwrotnosc_modulo(ll a, ll mod){
    return szybkie_potegowanie(a, mod-2, mod);
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    while (base < 2*n){
        base *= 2;
    }

    vector <int> drzewo(2*base, 0);
    vector <vector<int>> graf(n+1);
    for (int i = 1; i <= n; i++){
        int a, b;
        cin >> a >> b;
        int aq = query(a, drzewo);
        int bq = query(b, drzewo);
        if (aq != 0){
            graf[i].push_back(aq);
        }
        if (bq != 0){
            graf[i].push_back(bq);
        }
        update(a, b, i, drzewo);
    }

    //transpozycja grafu
    vector <vector<int>> grafT (n+1);
    for (int i = 1; i <= n; i++){
        for (int j = 0; j < graf[i].size(); j++){
            grafT[graf[i][j]].push_back(i);
        }
    }

    vector <int> dostepne(n+1, 0);
    for (int i = 1; i <= n; i++){
        vector <bool> odwiedzone(n+1, 0);
        odwiedzone[i] = 1;
        queue <int> kolejka;
        kolejka.push(i);
        while (!kolejka.empty()){
            int v = kolejka.front();
            kolejka.pop();
            for (int j = 0; j < grafT[v].size(); j++){
                if (odwiedzone[grafT[v][j]] == 0){
                    odwiedzone[grafT[v][j]] = 1;
                    kolejka.push(grafT[v][j]);
                }
            }
        }
        for (int j = 1; j <= n; j++){
            if (odwiedzone[j] == 1){
                dostepne[i]++;
            }
        }
    }

    ll akt_p = 1, akt_q = dostepne[1];
    for (int i = 2; i <= n; i++){
        pair<long, long> pom = dodawanie({akt_p, akt_q}, {1, dostepne[i]});
        akt_p = pom.first; akt_q = pom.second;
    }

    cout << ((akt_p%1000000007)*odwrotnosc_modulo(akt_q, 1000000007))%1000000007 << "\n";
}