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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1<<20;
const ll p = 1e9+7;
int n, t;
pair <int, int> tab[500005];
vector <int> sas[500005];
int x[500005];
pair <int, int> tree[2*N];
ll sil[500005];
ll ant[500005];
ll res;
int vis[500005];
ll pot_szybkie(ll a, ll m)
{
    ll w = 1;
    while (m)
    {
        if (m%2 == 1)
        {
            w *= a;
            w %= p;
        }
        a *= a;
        a %= p;
        m /= 2;
    }
    return w;
}
void update(int v, int val)
{
    v += N;
    tree[v] = {val, v - N};
    v /= 2;
    while (v)
    {
        tree[v] = max(tree[2*v], tree[2*v+1]);
        v /= 2;
    }
}
pair <int, int> query(int a, int b, int x = 0, int y = N-1, int v = 1)
{
    if (x > b || y < a) return {0, 0};
    if (x >= a && y <= b) return tree[v];
    return max(query(a, b, x, (x+y)/2, v*2), query(a, b, (x+y)/2+1, y, v*2+1));
}
void pre_process()
{
    sil[0] = 1;
    for (int i = 1; i <= n; ++i)
    {
        sil[i] = sil[i-1] * i;
        sil[i] %= p;
    }
    ant[n] = pot_szybkie(sil[n], p-2) % p;
    for (int i = n-1; i > 1; --i)
    {
        ant[i] = ant[i+1] * (i+1);
        ant[i] %= p;
    }
    ant[0] = ant[1] = 1;
}
int dfs(int v)
{
    vis[v] = t;
    int sum = 1;
    for (int i : sas[v])
    {
        if (vis[i] != t) sum += dfs(i);
    }
    return sum;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    pre_process();
    for (int i = 1; i <= n; ++i)
    {
        cin >> tab[i].first >> tab[i].second;
    }
    for (int i = n; i > 0; --i)
    {
        auto mx = query(tab[i].first, tab[i].second);
        while (mx.first > 0)
        {
            if (!sas[i].empty()) if (sas[i][sas[i].size()-1] != mx.first)
            {
                sas[i].push_back(mx.first);
            }
            if (sas[i].empty())
            {
                sas[i].push_back(mx.first);
            }
            update(mx.second, 0);
            mx = query(tab[i].first, tab[i].second);
        }
        update(tab[i].first, i);
        update(tab[i].second, i);
    }
    for (int i = 1; i <= n; ++i)
    {
        t = i;
        x[i] = dfs(i);
    }
    for (int j = 1; j <= n; ++j)
    {
        ll y = n - x[j], wyn = 0;
        for (int i = 1; i <= y; ++i)
        {
            wyn += ((sil[y]*ant[y-i])%p)*sil[n-i-1];
            wyn %= p;
        }
        res += wyn;
        res %= p;
    }
    res *= ant[n];
    res %= p;
    ++res;
    res%= p;
    cout << res;
}