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
125
126
127
128
129
130
131
132
133
#include <iostream>
#include <vector>
#include <string>
#include <numeric>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <tuple>
#include <unordered_set>

using namespace std;

const int MOD = 1e9 + 7;

long long fastPow(long long base, long long power)
{
    base %= MOD;
    long long result = 1;
    while (power > 0)
    {
        if (power & 1)
            result = (result * base) % MOD;
        base = (base * base) % MOD;
        power >>= 1;
    }
    return result;
}

long long findQ2(long long q)
{
    return fastPow(q, MOD - 2);
}

long long findNwd(long long a, long long b)
{
    while (b != 0)
    {
        long long t = b;
        b = a % b;
        a = t;
    }
    return a;
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n;
    std::cin >> n;

    vector<pair<int, int>> desks(n);
    vector<int> permutation(n);

    for (int i = 0; i < n; i++)
    {
        int start, end;
        std::cin >> start >> end;
        desks[i] = {start, end};
        permutation[i] = i;
    }

    long long perms = 0;
    long long actions = 0;
    do
    {
        vector<bool> flooded(n, false);
        int floodedCount = 0;

        for (int i = 0; i < n; i++)
        {
            int height = permutation[i];

            if (flooded[height])
            {
                continue;
            }

            actions++;
            flooded[height] = true;
            floodedCount++;

            auto desk = desks[height];

            set<int> waterFlow;

            waterFlow.insert(desk.first);
            waterFlow.insert(desk.second);

            for (int j = height - 1; j >= 0; j--)
            {
                auto desk2 = desks[j];

                auto left = desk2.first;
                auto right = desk2.second;

                auto lower = waterFlow.lower_bound(left);
                auto upper = waterFlow.upper_bound(right);

                if (lower != upper)
                {
                    waterFlow.erase(lower, upper);
                    waterFlow.insert(left);
                    waterFlow.insert(right);

                    flooded[j] = true;
                    floodedCount++;
                }
            }
        }

        perms++;
    } while (std::next_permutation(permutation.begin(), permutation.end()));

    long long p = actions;
    long long q = perms;

    long long nwd = findNwd(p, q);

    p /= nwd;
    q /= nwd;

    long long q2 = findQ2(q);

    long long result = (p * q2) % MOD;

    std::cout << result << std::endl;

    return 0;
}