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
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int l[500500];
int r[500500];

int perm[500500];

unordered_set<int> nbhs[500500];
unordered_map<int, bool> visited;

const ll mod = 1e9+7;

void dfs(int v) {
    if(visited[v]) {
        return;
    }
    visited[v] = true;

    for(auto u: nbhs[v]) {
        dfs(u);
    }
}

ll inv(ll a) {
  return a <= 1LL ? a : mod - (mod/a)*inv(mod%a)%mod;
}


int main() {
    int n;
    cin >> n;

    for(int i = 0; i < n; i++) {
        cin >> l[i] >> r[i];
        perm[i] = i;

        for(int j = i - 1; j >= 0; j--) {
            if((l[j] < l[i] && l[i] < r[j])) {
                nbhs[i].insert(j);
                break;
            }
        }

        for(int j = i - 1; j >= 0; j--) {
            if((l[j] < r[i] && r[i] < r[j])) {
                nbhs[i].insert(j);
                break;
            }
        }
    }

    ll on_taps = 0;
    ll all_taps = 0;
    do {
        for(int i = 0; i < n; i++) {
            if(!visited[perm[i]]) {
                dfs(perm[i]);
                on_taps++;
            }
        }
        visited.clear();
        all_taps++;
    } while(next_permutation(perm, perm + n));

    ll _gcd = gcd(on_taps, all_taps);
    on_taps /= _gcd;
    all_taps /= _gcd;

    cout << (on_taps*inv(all_taps))%mod << "\n";

    return 0;
}