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
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

typedef pair<int, int> pii;
typedef long long int ll;
typedef long long int LL;

const int MX = 100;
const ll mod = 1e9+7;

void dfs(bool [], int);
int count(const vector<int> &);

pii lvl[MX];
vector<int> adj[MX];

int count(const vector<int> &arr){
    int ret = 0;
    bool vis[MX] {};
    for(int p : arr){
        if(!vis[p]){
            ret++;
            dfs(vis, p);
        }
    }
    return ret;
}

void dfs(bool vis[], int x){
    if(vis[x])
        return;
    vis[x] = true;
    for(int y : adj[x])
        dfs(vis, y);
}

ll fast(ll a, ll p){
    ll res = 1;
    while(p > 0){
        if(p % 2 == 1)
            res = (a * res)%mod;
        a = (a*a)%mod;
        p /= 2;
    }
    return res;
}

int main(){
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> lvl[i].first >> lvl[i].second;
    }

    vector<int> kol;
    for(int i = 1; i <=n ;i++){
        kol.push_back(i);
    }

    vector<pii> drops;
    drops.push_back({lvl[n].first, n});
    drops.push_back({lvl[n].second, n});
    for(int i = n-1; i > 0; i--){
        for(int k = 0; k < drops.size(); k++){
            pii d = drops[k];
            if(d.first > lvl[i].first and d.first < lvl[i].second){
                adj[d.second].push_back(i);
                drops.erase(drops.begin()+k);
                k--;
            }
        }
        drops.push_back({lvl[i].first, i});
        drops.push_back({lvl[i].second, i});
    }

    ll res = 0;

    do{
        res += count(kol);
        res %= mod;
    }while(next_permutation(kol.begin(), kol.end()));

    ll fact = 1;
    for(int i = 2; i <= n; i++)
        fact *= i;

    ll pow = fast(fact, mod-2);
    pow *= res;


    cout << pow%mod;

    return 0;
}