link。

Lagrange Interpolation。

朴素的 dp 即设 $f_i(j)$ 表示前 $i$ 个位置，最大值为 $j$，位置 $i$ 可选可不选的方案数，转移即 $\displaystyle f_i(j) = f_{i-1}(j)+ [l_i \leqslant j \leqslant r_i]\sum_{k < j} f_{i-1}(k)$。把 $j$ 当作自变量，若没有 $l$，$r$ 的限制，则可以发现这是个多项式。加上 $l$，$r$，则是一个分段多项式。比如 $f_1(x) = [l_1 \leqslant x \leqslant r_1]$，$\displaystyle \sum_x f_1(x)$ 是分段多项式 $g_1(x)$，$f_2(x) = f_1(x) + [l_2 \leqslant x \leqslant r_2] g_1(x-1)$，每次前缀和加一次次数。

考虑如何削去 $l$，$r$ 的限制，我们可以像 codeforces - 1295f 一样，把区间们化成左闭右开并且把每一个端点当成“标兵”放到数轴上，对相邻标兵构成的区间段（同样是左闭右开）进行考察。容易发现，在同一个段中的多项式并没有分段，我们直接代入 $n+1$ 个点值，就可以确定这个最多 $n$ 次的多项式。

注意，当我们把区间端点离散化后，我们 dp 的状态就变了，$f_i(j)$ 的意义成为了前 $i$ 个位置，前 $j$ 个区间段（注意是值域）拉通了来看的方案数，即多项式在末尾处的取值。

看到我们研究的这个 $j$，段 $j$ 本身就是一个连续的多项式函数，我们需要从段 $j-1$ 的末尾转移过来，这就是为什么我们要求的是段 $j$ 末尾的函数值，即后面的转移需要用。

感觉说得不是很清楚，建议自己再画画图……

const int md = 1e9 + 7;
il int add(int x, int y) {
      if ((x += y) >= md)
    x -= md;
  return x;
}
il int sub(int x, int y) {
      if ((x -= y) < 0)
    x += md;
  return x;
}
il int mul(int x, int y) { return static_cast<long long>(x) * y % md; }
template <class T, class... P> il T mul(T x, T y, P... args) {
      return mul(x, mul(y, args...));
}
il void adds(int &x, int y) {
      if ((x += y) >= md)
    x -= md;
}
il void muls(int &x, int y) { x = static_cast<long long>(x) * y % md; }
int pow(int x, int y) {
      int z(1);
  for (; y; y >>= 1, muls(x, x))
    if (y & 1)
      muls(z, x);
  return z;
}
il int sgn(int n) { return n % 2 ? md - 1 : 1; }
int n, l[1 << 9], r[1 << 9], dat[2 << 9], tot, rec[2 << 9][1 << 9], sum[2 << 9],
    ifct[1 << 9], dp[2 << 9];
int p[1 << 9], q[1 << 9];
int fit(int t, int y[]) {
      int res = 0;
  p[0] = q[n + 2] = 1;
  rep(i, 1, n + 2) p[i] = mul(p[i - 1], sub(t, i));
  drep(i, n + 2, 1) q[i] = mul(q[i + 1], sub(t, i));
  rep(i, 1, n + 2) adds(res, mul(ifct[i - 1], ifct[n + 1 - i], sgn(n - i + 1),
                                 p[i - 1], q[i + 1], y[i]));
  return res;
}
signed main() {
      ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n;
  ifct[0] = 1;
  rep(i, 1, n + 2) ifct[i] = mul(ifct[i - 1], i);
  rep(i, 1, n + 2) ifct[i] = pow(ifct[i], md - 2);
  rep(i, 1, n + 1) cin >> l[i] >> r[i];
  rep(i, 1, n + 1) dat[++tot] = l[i], dat[++tot] = ++r[i];
  sort(dat + 1, dat + tot + 1);
  tot = unique(dat + 1, dat + tot + 1) - dat - 1;
  rep(i, 1, n + 1) l[i] = lower_bound(dat + 1, dat + tot + 1, l[i]) - dat;
  rep(i, 1, n + 1) r[i] = lower_bound(dat + 1, dat + tot + 1, r[i]) - dat;
  rep(i, tot + 1) sum[i] = 1;
  rep(i, 1, n + 1) {
        rep(j, l[i], r[i]) {
          rep(k, 1, n + 2) adds(rec[j][k], sum[j - 1]);
      rep(k, 2, n + 2) adds(rec[j][k], rec[j][k - 1]);
      dp[j] = fit(dat[j + 1] - dat[j], rec[j]);
    }
    rep(j, 1, tot + 1) sum[j] = add(sum[j - 1], dp[j]);
  }
  cout << sum[tot] - 1 << \"\n\";
}