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
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define fi first
#define se second
#define pn printf("\n")
#define ssize(x) int(x.size())
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define bitcount(x) __builtin_popcount(x)
#define clz(x) __builtin_clz(x)
#define ctz(x) __builtin_ctz(x)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
typedef double db;
typedef long double ldb;
#define vv vector
/*void read(int &a){
		char c = getchar_unlocked(); a = 0;
		while(c<'0' || '9'<c) c = getchar_unlocked();
		while('0'<=c&&c<='9') a = (a<<3)+(a<<1)+c-'0', c = getchar_unlocked();
}*/
int inf = 2e09; ll infll = 2e18; int mod = 1e09+7;
int add(int a, int b){return a+b >= mod ? a+b - mod : a+b;}
int sub(int a, int b){return a-b < 0 ? a-b + mod : a-b;}
int mul(int a, int b){return int(a * ll(b) % mod);}
int fpow(int a, int b){
		int ret = 1;
		while(b){
				if(b & 1) ret = mul(ret, a);
				b >>= 1, a = mul(a, a);
		} return ret;
}
int inv(int a){ return fpow(a, mod-2); }
int coeff(int n, int k, vector<int> &fac, vector<int> &invfac){
		if(n < k) return 0;
		return mul(fac[n], mul(invfac[n-k], invfac[k]));
}
void calcfac(int n, vector<int> &fac, vector<int> &invfac){
		fac[0] = 1, invfac[0] = 1;
		for(int i = 1; i <= n; ++i) fac[i] = mul(fac[i-1], i);
		invfac[n] = inv(fac[n]);
		for(int i = n-1; i; --i) invfac[i] = mul(invfac[i+1], i+1);
}
const int MAXLEN = 500000;
template<int len = 1>
void answer(int n){
		if(len < n) return void(answer<min(len<<1, MAXLEN)>(n));
		//~ printf("%d\n", len);
		vv<vv<int>> g(n+1);
		vv<pii> t(n+1);
		for(int i = 1; i <= n; ++i) scanf("%d%d", &t[i].fi, &t[i].se);
		reverse(1+all(t));
		set<pii> s;
		for(int i = 1; i <= n; ++i){
				int l = t[i].fi, r = t[i].se; //scanf("%d%d", &l, &r);
				//~ printf("%d %d\n", l, r);
				auto it = s.lower_bound(pii(l, 0));
				int prev = 0;
				while(it != s.end() && (*it).fi <= r){
						if((*it).se != prev) g[i].emplace_back((*it).se);//, printf("%d %d\n", i, (*it).se);
						prev = (*it).se;
						it = s.erase(it);
				}
				s.emplace(pii(l, i)), s.emplace(pii(r, i));
		}
		vv<int> pow2(n+1, 0), fac(n+1, 0), invfac(n+1, 0); pow2[0] = 1; calcfac(n, fac, invfac);
		for(int i = 1; i <= n; ++i) pow2[i] = mul(2, pow2[i-1]);
		vv<int> vis(n+1, 0), dp(n+1, 0);
		vector<bitset<len>> bs(n+1);
		int result = 0;
		for(int i = 1; i <= n; ++i){
				//~ printf("%d\n", i);
				for(int j = i; j; --j) vis[j] = 0;
				int x = -1; vis[i] = 1;
				if(ssize(g[i]) == 1) bs[i] = bs[g[i].back()];
				else for(int u : g[i]) bs[i] |= bs[u];
				
				x = int(bs[i].count()), bs[i][i-1] = 1;
				dp[i] = x;
				int res = mul(fac[n], inv(x+1));
				//~ printf("%d\n", x);
				result = add(result, res);
		}
		result = mul(result, inv(fac[n]));
		printf("%d\n", result);
}
signed main(){
		int T = 1;
		//~ scanf("%d", &T);
		//~ ios_base::sync_with_stdio(0); cin.tie(0); //cin >> T;
		for(++T; --T; ){
				int n; scanf("%d", &n);
				answer<1>(n);
		}
		return 0;
}