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
#include <bits/stdc++.h>

using namespace std;

const int N = 500'000 + 7;

const int mod = 1e9 + 7;

int add(int a, int b) {
	return a += b, a < mod ? a : a - mod;
}

int mul(int a, int b) {
	return int(1LL * a * b % mod);
}

int pot(int a, int b) {
	int r = 1;
	for (; b; b >>= 1, a = mul(a, a))
		if (b & 1)
			r = mul(r, a);
	return r;
}

int fac[N], ifac[N];

int n, l[N], r[N], ile[N];
vector<pair<int, int>> edges;

const int B = 1 << 10;
bitset<B> gdzie[N];

int main() {
	ios::sync_with_stdio(false), cin.tie(nullptr);

	cin >> n;

	fac[0] = 1;
	for (int i = 1; i <= n; i++)
		fac[i] = mul(fac[i - 1], i);

	ifac[n] = pot(fac[n], mod - 2);
	for (int i = n - 1; i >= 0; i--)
		ifac[i] = mul(ifac[i + 1], i + 1);

	for (int i = 1; i <= n; i++)
		cin >> l[i] >> r[i];

	set<pair<int, int>> krany;

	for (int i = n; i >= 1; i--) {
		auto it = krany.lower_bound(make_pair(l[i], -1));

		vector<pair<int, int>> to_delete;
		while (it != krany.end() &&
			   it->first <= r[i]) {

			edges.emplace_back(i, it->second);
			to_delete.push_back(*it);
			it++;
		}

		for (auto p : to_delete)
			krany.erase(p);

		krany.emplace(l[i], i);
		krany.emplace(r[i], i);
	}

	sort(edges.begin(), edges.end());
	edges.erase(unique(edges.begin(), edges.end()), edges.end());
	reverse(edges.begin(), edges.end());

	for (int block = 1; block <= n; block += B) {
		for (int i = 1; i <= n; i++)
			gdzie[i].reset();

		for (int i = 0; i < min(B, n - block + 1); i++)
			gdzie[block + i].set(i);

		for (auto [a, b] : edges)
			gdzie[a] |= gdzie[b];

		for (int i = 1; i <= n; i++)
			ile[i] += (int) gdzie[i].count();
	}

	int ans = 0;

	for (int i = 1; i <= n; i++) {
		ile[i]--;

		int now = 1;

		now = mul(now, fac[n]);
		now = mul(now, n - ile[i]);
		now = mul(now, pot(ile[i] + 1, mod - 2));
		now = mul(now, ifac[n - ile[i]]);

		ans = add(ans, mul(now, fac[n - ile[i] - 1]));
	}

	cout << mul(ans, ifac[n]) << '\n';
}