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
#include <bits/stdc++.h>
using namespace std;
 
#ifdef DEBUG
auto &operator<<(auto &o, pair<auto, auto> p) {
    return o << "()" << p.first << ", " << p.second <<")";
}
auto operator<<(auto &o, auto x)-> decltype(x.end(), o) {
    o << "{";int i = 0;
    for(auto e : x) o << ", "+!i++<<e;
    return o <<"}";
}
#define debug(x...) cerr << "["#x"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(x)
#else
#define debug(...) {}
#endif
 
#define all(x) x.begin(), x.end()
#define pb push_back
#define fi first
#define se second
typedef pair <int, int> pii;

const long long MOD = 1e9+7;
const int maxn = 3e3+7;
long long C[maxn + 7][maxn + 7];
long long fact[maxn+7];

long long qpow(long long a, int b) {
    if (b == 0) return 1ll;
    if (b & 1) {
        return (a * qpow(a, b-1))%MOD;
    }
    long long x = qpow(a, b/2);
    return (x*x)%MOD;
}

int to_rem[maxn*2];

 
void test() {
    int n; cin>>n;
    vector <pii> p(n);
    
    for (int i=0; i<n; ++i) {
        cin>>p[i].fi>>p[i].se;
    }

    vector <int> zal(n);

    for (int i=n-1; i>=0; --i) {
        set <int> punkty;
        punkty.insert(p[i].fi);
        punkty.insert(p[i].se);
    
        for (int j=i-1; j>=0; --j) {
            auto px = punkty.lower_bound(p[j].fi);
            if(px != punkty.end() && (*px) <= p[j].se) {
                int it = 0;
                while (px != punkty.end() && (*px) <= p[j].se) {
                    to_rem[it] = (*px);
                    it++;
                    px = next(px);
                }
                for (int k=0; k<it; ++k) {
                    punkty.erase(to_rem[k]);
                }
                punkty.insert(p[j].fi);
                punkty.insert(p[j].se);
                zal[j]++;
            }
        }
    }

    long long res = 0;

    for (int i=0; i<n; ++i) {
        for (int pos=0; pos<n; ++pos) {
            int dost = n-zal[i]-1;
            if (dost < 0) continue;

            long long wybor = C[dost][pos];
            int pozostali = n-pos-1;
            debug(wybor, fact[pozostali], fact[pos]);
            res = (res + (((fact[pozostali]*wybor)%MOD) * fact[pos])%MOD)%MOD; 
        }
    }

    cout<<(res * qpow(fact[n], MOD-2))%MOD<<'\n';
}
 
signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int t = 1; 

    C[0][0] = 1;
    fact[0] = 1;
    for (long long n = 1; n <= maxn; ++n) {
        fact[n] = (fact[n-1]*n)%MOD;
        C[n][0] = C[n][n] = 1;
        for (int k = 1; k < n; ++k)
            C[n][k] = (C[n - 1][k - 1] + C[n - 1][k])%MOD;
    }

    while (t--) {
      test();
    }
}