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
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;

const LL MOD = 1e9 + 7;

const int M = 1 << 21;
pair<int, int> T[M * 2 + 5];

void update(int a, int b, LL v, int hist) {
	a += M;
	b += M;
	T[a] = {v, hist};
	T[b] = {v, hist};
	while (a / 2 != b / 2) {
		if ((a & 1) == 0) {
			T[a + 1] = {v, hist};
		}
		if ((b & 1) == 1) {
			T[b - 1] = {v, hist};
		}
		a /= 2;
		b /= 2;
	}
}

int query(int a) {
	a += M;
	auto res = T[a];
	while (a != 1) {
		if (T[a].second > res.second) {
			res = T[a];
		}
		a /= 2;
	}
	return res.first;
}

LL gcd(LL a, LL b, LL& x, LL& y) {
	x = 1, y = 0;
	LL x1 = 0, y1 = 1, a1 = a, b1 = b;
	while (b1) {
		LL q = a1 / b1;
		tie(x, x1) = make_tuple(x1, x - q * x1);
		tie(y, y1) = make_tuple(y1, y - q * y1);
		tie(a1, b1) = make_tuple(b1, a1 - q * b1);
	}
	return a1;
}

pair<int, int> v[500009];
pair<int, int> hist[500009];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		int a, b;
		cin >> a >> b;
		hist[i] = {a, b};
		int A = query(a);
		int B = query(b);
		if (A != 0) {
			v[i].first = A;
		}
		if (A != B && B != 0) {
			v[i].second = B;
		}
		update(a, b, i, i);
	}
	vector<vector<ULL>> V(n + 1);
	for (int i = 0; i < n; i++) {
		V[i].resize(i / 64 + 1);
	}

	LL q = 1;
	for (LL i = 2; i <= n; i++) {
		q = (q * i) % MOD;
	}

	LL qq, tmp;
	gcd(q, MOD, qq, tmp);
	qq = (qq + MOD) % MOD;

	LL res = 0;
	for (int i = n; i > 0; i--) {
		const int id = n - i;
		const int idx = id / 64;
		const int idxm = id % 64;
		int x = 0;

		for (int l = 0; l <= idx; ++l) {
			x += popcount(V[id][l]);
		}

		x++;
		LL X;
		gcd(x, MOD, X, tmp);
		X = (X + MOD) % MOD;
		res = (res + q * X) % MOD;

		if (v[i].first != 0) {
			const int jd = n - v[i].first;
			V[jd][idx] |= 1LL << idxm;
			for (int l = 0; l <= idx; ++l) {
				V[jd][l] |= V[id][l];
			}
		}
		if (v[i].second != 0) {
			const int jd = n - v[i].second;
			V[jd][idx] |= 1LL << idxm;
			for (int l = 0; l <= idx; ++l) {
				V[jd][l] |= V[id][l];
			}
		}
	}
	cout << (res * qq + MOD) % MOD << "\n";
	return 0;
}