rt。拉插。TLE 85 pts。

#include <bits/stdc++.h>

#define rep(i,l,r) for (int i = l; i <= r; i++)
#define per(i,r,l) for (int i = r; i >= l; i--)
#define fi first
#define se second
#define pb push_back
#define mp std::make_pair
#define gin std::cin
#define prt std::cout
#define edl std::endl

namespace Main {
  const int N = 305,mod = 1e9 + 7;
  int n,pre[N],suf[N],invfac[N];
  int A[N],B[N];
  std::vector<int> a;
  int y[2][2205][N];
  int id[N][N],f[305][2205],tot;
  bool vis[305][2205],flag[N][N];
  std::vector<std::pair<int,int>> range;
  inline int lag(int len,int x,int y[]) {
    if (x <= len) return y[x]; 
    pre[0] = suf[len + 1] = 1;
    rep(i,1,len) pre[i] = 1ll * pre[i - 1] * (x - i + mod) % mod;
    per(i,len,1) suf[i] = 1ll * suf[i + 1] * (x - i + mod) % mod;
    int res = 0;
    rep(i,1,len) {
      int cur = y[i];
      if (cur == 0) continue; 
      cur = 1ll * cur * pre[i - 1] % mod * suf[i + 1] % mod;
      cur = 1ll * cur * invfac[i - 1] % mod * invfac[len - i] % mod;
      if ((len - i) & 1) cur = (mod - cur) % mod;
      res = (res + cur) % mod;
    }
    return res;
  } 
  void dfs(int l,int r) {
    if (l > r) return;
    if (flag[l][r]) return;
    flag[l][r] = true;
    id[l][r] = ++ tot; range.push_back({l,r});
    rep(k,l,r) if (abs((k - l) - (r - k)) <= 2) {
      dfs(l,k - 1); dfs(k + 1,r);
    }
  }
  int DP(int l,int r,int i,int j) {
    if (l > r) return 1;
    if (vis[j][id[l][r]]) return f[j][id[l][r]];
    vis[j][id[l][r]] = true;
    if (j == 0) {
      if (i == 0) {
        f[j][id[l][r]] = 0;
        return f[j][id[l][r]];
      }
      if (a[i] - a[i - 1] <= n + 1) {
        f[j][id[l][r]] = y[(i - 1) & 1][id[l][r]][a[i] - a[i - 1]];
      } else f[j][id[l][r]] = lag(r - l + 2,a[i] - a[i - 1],y[(i - 1) & 1][id[l][r]]); 
      return f[j][id[l][r]];
    }
    f[j][id[l][r]] = DP(l,r,i,j - 1);
    int mid = (l + r) >> 1;
    for (int k = std::max(l,mid - 1); k <= std::min(r,mid + 1); k++) {
      if (a[i] + j - 1 < A[k] || a[i] + j - 1 > B[k]) continue;
      if (abs((r - k) - (k - l)) > 2) continue;
      int ls = DP(l,k - 1,i,j),rs = DP(k + 1,r,i,j - 1);
      if (!ls || !rs) continue; 
      f[j][id[l][r]] = (1ll * f[j][id[l][r]] + 1ll * DP(l,k - 1,i,j) * DP(k + 1,r,i,j - 1) % mod) % mod;
    }
    y[i & 1][id[l][r]][j] = f[j][id[l][r]];
    return f[j][id[l][r]];
  }
  void main() {
    scanf("%d",&n); rep(i,1,n) scanf("%d%d",&A[i],&B[i]);
    invfac[0] = invfac[1] = 1; rep(i,2,n + 1) invfac[i] = 1ll * (mod - mod / i) * invfac[mod % i] % mod;
    rep(i,2,n + 1) invfac[i] = 1ll * invfac[i - 1] * invfac[i] % mod;
    rep(i,1,n) {
      a.push_back(A[i]); a.push_back(B[i] + 1);
    } dfs(1,n);
    std::sort(a.begin(),a.end()); a.erase(std::unique(a.begin(),a.end()),a.end());
    for (int i = 0; i + 1 < (int)a.size(); i++) {
      memset(vis,false,sizeof vis);
      for (auto j : range) {
        per(k,std::min(a[i + 1] - a[i],n + 1),1) DP(j.first,j.second,i,k); 
      }
    }
    int k = (int)a.size() - 2; printf("%d",lag(n + 1,a[k + 1] - a[k],y[k & 1][id[1][n]]));
  }
} signed main() { Main::main(); return 0; }