#include #include #include #include #include #include #include #include #include #include using namespace std; #define int long long int MOD = 1000000007; template struct comb_util { std::array fc, ifc; comb_util() { fc[0] = 1; for (int i = 1; i <= N; i++) fc[i] = fc[i - 1] * i % MOD; ifc[N] = inv(fc[N]); for (int i = N - 1; i >= 0; i--) ifc[i] = ifc[i + 1] * (i + 1) % MOD; } Int fact(Int n) { return fc[n]; } Int inv_fact(Int n) { return ifc[n]; } Int inv(Int n) { return pow(n, MOD - 2); } Int pow(Int n, Int a) { Int res = 1, exp = n; for (; a; a /= 2) { if (a & 1) res = res * exp % MOD; exp = exp * exp % MOD; } return res; } Int perm(Int n, Int r) { if (r < 0 || n < r) return 0; else return fc[n] * ifc[n - r] % MOD; } Int binom(Int n, Int r) { if (n < 0 || r < 0 || n < r) return 0; return fc[n] * ifc[r] % MOD * ifc[n - r] % MOD; } Int homo(Int n, Int r) { if (n < 0 || r < 0) return 0; return r == 0 ? 1 : binom(n + r - 1, r); } }; using comb = comb_util; comb cb; void add(int &a, const int &b) { a += b; if (a >= MOD)a -= MOD; } signed main() { cin.tie(0); ios::sync_with_stdio(false); int N; cin >> N; vector A(N), B(N); int res = 0; set st; vector X; map mp; for (int i = 0; i < N; i++) { cin >> A[i] >> B[i]; st.insert(A[i]); st.insert(B[i]); } for (auto s : st) { mp[s] = X.size(); X.push_back(s); } int M = X.size(); vector > C(N + 1, vector(N + 1, 0)); C[0][0] = 1; for (int i = 1; i <= N; i++) { int sum = 0; int b = cb.inv(i + 1); if (i % 2 == 1) { for (int j = 0; j <= i; j++) { add(C[i][j], (b * sum) % MOD); add(sum, C[i - 1][j]); } } else { for (int j = i; j >= 0; j--) { add(sum, C[i - 1][j]); add(C[i][j], (b * sum) % MOD); } } } vector D(N); for (int i = 0; i < N; i++) { D[i] = 0; for (int j = 0; j <= N; j++) { add(D[i], C[i + 1][j]); } //cerr << i << " " << D[i] << endl; } vector E(N); for (int i = 0; i < N; i++) { E[i] = 1; if (i > 0) { E[i] = cb.inv(D[i - 1]); } E[i] = (E[i] * D[i]) % MOD; } //cerr << (E[0] * E[1]) % MOD << endl; vector > dp(M - 1, vector(N, 0)); int l = mp[A[0]]; int r = mp[B[0]]; int b = cb.inv(B[0] - A[0]); for (int i = l; i < r; i++) { dp[i][0] = b * (X[i + 1] - X[i]) % MOD; } int inv2 = (MOD + 1) / 2; for (int i = 1; i < N; i++) { vector > ndp(M - 1, vector(N, 0)); l = mp[A[i]]; r = mp[B[i]]; b = cb.inv(B[i] - A[i]); if (i % 2 == 1) { int sum = 0; for (int j = 0; j < M - 1; j++) { if (l <= j && j < r) { int tt = ((X[j + 1] - X[j]) * b) % MOD; add(ndp[j][0], tt * sum % MOD); for (int k = 0; k < N - 1; k++) { add(ndp[j][k + 1], ((tt * dp[j][k] % MOD) * E[k]) % MOD); } } for (int k = 0; k < N; k++) { add(sum, dp[j][k]); } } } else { int sum = 0; for (int j = M - 2; j >= 0; j--) { if (l <= j && j < r) { int tt = ((X[j + 1] - X[j]) * b) % MOD; add(ndp[j][0], tt * sum % MOD); for (int k = 0; k < N - 1; k++) { add(ndp[j][k + 1], ((tt * dp[j][k] % MOD) * E[k]) % MOD); } } for (int k = 0; k < N; k++) { add(sum, dp[j][k]); } } } swap(dp, ndp); } for (int i = 0; i < M - 1; i++) { for (int j = 0; j < N; j++) { add(res, dp[i][j]); } } cout << res << endl; }