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
// clang-format off
#include<bits/stdc++.h>
using namespace std;
using LL=long long;
#define FOR(i,l,r) for(auto i=(l);i<=(r);++i)
#define REP(i,n) FOR(i,0,(n)-1)
#define ssize(x) int(x.size())
template<class A,class B>auto&operator<<(ostream&o,pair<A,B>p){return o<<"("<<p.first<<", "<<p.second<<")";}
template<class T>auto operator<<(ostream&o,T x)->decltype(x.end(),o){o<<"{";int i=0;for(auto e:x)o<<(", ")+2*!i++<<e;return o<<"}";}
#ifdef DEBUG
#define debug(x...) cerr<<"["#x"]: ",[](auto...$){((cerr<<$<<"; "),...);}(x),cerr<<'\n'
#else
#define debug(...) {}
#endif
// clang-format on

// clang-format off
const int MOD = 1000000007;
int add(const int& a, const int& b) { return (a + b >= MOD ? a + b - MOD : a + b); }
int mul(const int& a, const int& b) { return 1LL * a * b % MOD; }
int fast_pow(int base, int exp);
// clang-format on

int
main()
{
    cin.tie(0)->sync_with_stdio(0);
    int n;
    cin >> n;
    if (n > 50) {
        cout << "0\n";
        return 0;
    }

    using mask_t = uint64_t;
    vector<mask_t> covers(n + 1);
    vector<int> floor(n * 2 + 1);
    FOR (h, 1, n) {
        int l, r;
        cin >> l >> r;
        covers[h] = (mask_t)1 << h;
        covers[h] |= covers[floor[l]] | covers[floor[r]];
        FOR (i, l, r) floor[i] = h;
    }

    // For each permutation, count the number of used taps
    int total_used = 0;
    vector<int> perm(n);
    iota(perm.begin(), perm.end(), 1);
    do {
        mask_t covered = 0;
        REP (i, n) {
            const auto& v = perm[i];
            if ((covered >> v) & 1) continue;
            total_used += 1;
            covered |= covers[v];
        }
        if (total_used >= MOD) total_used -= MOD;
        debug(perm, total_used);
    } while (next_permutation(perm.begin(), perm.end()));

    // Calculate the total number of permutations
    int total_perms = 1;
    FOR (i, 2, n) total_perms = mul(total_perms, i);

    // Output the score
    cout << mul(total_used, fast_pow(total_perms, MOD - 2)) << "\n";
    return 0;
}

int
fast_pow(int base, int exp)
{
    int res = 1;
    while (exp) {
        if (exp & 1) res = mul(res, base);
        base = mul(base, base);
        exp >>= 1;
    }
    return res;
}