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

#define int int64_t
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

const int MAXN = 50'009;
const int MOD = 1e9+7;

int fact[MAXN];
int fact_inv[MAXN];

struct SegTree {
	const static int T = 1<<17;
	pii t[2*T];
	void update(int l, int r, pii val) {
		l+=T, r+=T;
		t[l] = max(t[l], val);
		t[r] = max(t[r], val);
		while(l/2!=r/2) {
			if(l%2==0) t[l+1] = max(t[l+1], val);
			if(r%2==1) t[r-1] = max(t[r-1], val);
			l/=2;
			r/=2;
		}
	}
	int query(int x) {
		x+=T;
		pii ret = {0, 0};
		while(x) {
			ret = max(ret, t[x]);
			x/=2;
		}
		return ret.nd;
	}
} seg;

vector<int> G[MAXN];
int din[MAXN], dout[MAXN];

int C(int a, int b) {
	return fact[a]*fact_inv[b]%MOD*fact_inv[a-b]%MOD;
}

int f(int a, int b) {
	int c = 1;
	while(b) {
		if(b%2)
			c = c*a%MOD;
		a = a*a%MOD;
		b/=2;
	}
	return c;
}

pii tab[MAXN];
bool vis[MAXN];

bitset<MAXN> dp[MAXN];
int ans;
int n;

void dfs(int x) {
	vis[x] = true;
	for(int y:G[x]) {
		if(!vis[y]) dfs(y);
		dp[x][y] = 1;
		dp[x] |= dp[y];
	}
	int X = dp[x].count();
	ans += fact[X]*fact[n-X-1]%MOD*C(n, X+1);
	ans %= MOD;
}

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

	fact[0] = 1;
	for(int i=1;i<MAXN;i++) fact[i] = fact[i-1]*i%MOD;
	fact_inv[MAXN-1] = f(fact[MAXN-1], MOD-2);
	for(int i=MAXN-2;i>=0;i--) fact_inv[i] = fact_inv[i+1]*(i+1)%MOD;
	
	cin >> n;
	for(int i=1;i<=n;i++) {
		int l, r;
		cin >> l >> r;
		tab[i] = {l, r};
		int x = seg.query(l), y = seg.query(r);
		if(x) {
			G[x].pb(i);
			din[i]++;
		}
		if(y&&x!=y) {
			G[y].pb(i);
			din[i]++;
		}
		seg.update(l, r, {i, i});
	}
	for(int i=1;i<=n;i++) {
		if(din[i]==0) {
			dfs(i);
		}
	}
	cout << ans*fact_inv[n]%MOD << "\n";
}