#include <bits/stdc++.h> using namespace std; using ll = long long; const int mod = 1e9 + 7; const int maxn = 505; // Sửa lại maxn thành 505 int n, a[maxn], b[maxn]; ll inv[maxn]; vector<int> X; ll dp[maxn][maxn * 2]; // dp[i][j]: trường i chọn thuyền ở khoảng j ll pref[maxn][maxn * 2]; // pref[i][j]: tổng dp[0..i][0..j] // Tính nghịch đảo modulo ll pw(ll a, ll b) { ll res = 1; a %= mod; while (b > 0) { if (b % 2 == 1) res = res * a % mod; a = a * a % mod; b /= 2; } return res; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n; X.push_back(-1); // dummy for (int i = 1; i <= n; i++) { cin >> a[i] >> b[i]; X.push_back(a[i] - 1); X.push_back(b[i]); } sort(X.begin(), X.end()); X.erase(unique(X.begin(), X.end()), X.end()); for (int i = 1; i <= n; i++) inv[i] = pw(i, mod - 2); // Khởi tạo: pref[i][j] = 1 nghĩa là có 1 cách để "không chọn gì cả" for (int j = 0; j < X.size(); j++) pref[0][j] = 1; for (int j = 1; j < (int)X.size(); j++) { int L = X[j] - X[j-1]; if (L <= 0) continue; for (int i = 1; i <= n; i++) { if (a[i] <= X[j-1] + 1 && b[i] >= X[j]) { // Trường i có thể nằm trong khoảng j ll combo = L; // Tương đương C(L+1-1, 1) int cnt = 1; for (int p = i - 1; p >= 0; p--) { // Những cách xếp các trường trước đó ở các khoảng TRƯỚC j ll ways = (pref[p][j-1] * combo) % mod; dp[i][j] = (dp[i][j] + ways) % mod; // Nếu trường p cũng có thể nằm trong khoảng j, tăng cnt if (a[p] <= X[j-1] + 1 && b[p] >= X[j]) { cnt++; // Cập nhật combo: C(L+cnt-1, cnt) // Công thức: C(L+k-1, k) = C(L+k-2, k-1) * (L+k-1) / k combo = combo * (L + cnt - 1) % mod * inv[cnt] % mod; } } } } // Cập nhật pref sau khi đã tính xong tất cả i cho khoảng j hiện tại for (int i = 1; i <= n; i++) { pref[i][j] = (pref[i-1][j] + pref[i][j-1] - pref[i-1][j-1] + dp[i][j] + mod) % mod; } } ll ans = 0; for (int i = 1; i <= n; i++) { for (int j = 1; j < X.size(); j++) ans = (ans + dp[i][j]) % mod; } cout << ans << endl; return 0; }