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

using namespace std;

#define int long long

constexpr int modul = 1000 * 1000 * 1000 + 7;

// https://cp-algorithms.com/algebra/extended-euclid-algorithm.html
int extended_euclidean(int a, int b, int& x, int& y) {
    x = 1, y = 0;
    int x1 = 0, y1 = 1, a1 = a, b1 = b;
    while (b1) {
        int q = a1 / b1;
        tie(x, x1) = make_tuple(x1, x - q * x1);
        tie(y, y1) = make_tuple(y1, y - q * y1);
        tie(a1, b1) = make_tuple(b1, a1 - q * b1);
    }
    return a1;
}

// https://cp-algorithms.com/algebra/module-inverse.html
int inv(int a) {
  return a <= 1 ? a : modul - (modul/a) * inv(modul % a) % modul;
}

void solve() {
    int n;
    cin >> n;
    vector<int> l(n), r(n);
    for (int i = 0; i < n; i++) {
        cin >> l[n - i - 1] >> r[n - i - 1];
    }
    vector<vector<int>> g(n);
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if ((l[j] < l[i] && r[j] > l[i]) || (l[j] < r[i] && r[j] > r[i])) {
                g[i].push_back(j);
            }
        }
    }

    int res = 0;
    vector<int> perm(n);
    iota(perm.begin(), perm.end(), 0);
    vector<bool> vis(n);
    do {
        fill(vis.begin(), vis.end(), 0);
        for (int i : perm) {
            if (vis[i]) continue;
            vis[i] = true;
            res++;
            for (int next : g[i]) {
                vis[next] = true;
            }
        }
        if (res >= modul) res -= modul;
    } while(next_permutation(perm.begin(), perm.end()));
    int denom = 1;
    for (int i = 1; i <= n; i++) {
        denom *= i;
        denom %= modul;
    }
// cerr << res << " " << denom << endl;
    int x, y;
    int gcdv = extended_euclidean(res, denom, x, y);
    int gcdinv = inv(gcdv);
    res *= gcdinv;
    res %= modul;
    denom *= gcdinv;
    denom %= modul;
    cout << (res * inv(denom)) % modul << endl;

}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

// #ifdef LOCAL
//     int t; cin >> t; while (t--)
// #endif

    solve();

    cout.flush();
}