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
#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<ll,int> pli;
typedef pair<int,ll> pil;
typedef pair<int,int> pii;
const ll INFLL=1e18+7;
const int INF=1e9+7;
#define pb push_back
const int MAXN = 5e4+7;
int l[MAXN], r[MAXN];
map<pii, bool> conn;
vector<int> G[MAXN];
bitset<MAXN> reachable[MAXN];
bool visited[MAXN];
vector<int> postorder;
void DFS(int x){
    visited[x] = 1;
    for(int &v:G[x]) if(!visited[v]) DFS(v);
    postorder.pb(x);
}
int cnt[MAXN];
const int MOD = 1e9+7;
ll fact[MAXN];
ll inv_fact[MAXN];
int mod_pow(int x, int p, int m){
    ll res = 1, curr = x;
    for(int i=0;i<31;++i){
        if((1<<i) & p) res = res*curr%m;
        curr = curr*curr%m;
    }
    return res;
}
int main()
{
	ios_base::sync_with_stdio(0);
    int n; cin>>n;
    for(int i=1;i<=n;++i) cin>>l[n-i+1]>>r[n-i+1];
    set<pii> points;
    for(int i=1;i<=n;++i){
        auto it = points.upper_bound({l[i], -1});
        if(it != points.end()){
            auto it2 = points.upper_bound({r[i], INF});
            if(it2 != it){
                vector<pii> to_del;
                while(it != it2){
                    --it2;
                    to_del.pb(*it2);
                }
                for(pii &v:to_del){
                    if(!conn.count({i, v.second})){
                        conn[{i, v.second}] = 1;
                        G[i].pb(v.second);
                    }
                    points.erase(v);
                }
            }
        }
        points.insert({l[i], i});
        points.insert({r[i], i});
    }
    for(int i=1;i<=n;++i) reachable[i][i] = 1;
    for(int i=1;i<=n;++i) if(!visited[i]) DFS(i);
    for(int &v:postorder){
        for(int &w:G[v]){
            reachable[v] |= reachable[w];
        }
    }
    for(int i=1;i<=n;++i) cnt[i] = reachable[i].count() - 1;
    fact[0] = 1;
    for(int i=1;i<=n;++i) fact[i] = fact[i-1]*i%MOD;
    inv_fact[n] = mod_pow(fact[n], MOD-2, MOD);
    for(int i=n-1;i>=0;--i) inv_fact[i] = inv_fact[i+1]*(i+1)%MOD;
    ll ans = 0;
    for(int i=1;i<=n;++i){
        int k = cnt[i];
        ll total = fact[n]*inv_fact[n-k-1]%MOD;
        total = total*mod_pow(k+1, MOD-2, MOD)%MOD;
        total = total*fact[n-k-1]%MOD;
        ans += total;
        if(ans >= MOD) ans -= MOD;
    }
    cout<<ans*inv_fact[n]%MOD<<"\n";
}