1. Двумерное $dp[i][x]$ — количество последовательностей $c$ длины $i$, если для первых $i-1$ выполняется $a_{i^{\prime }}\le c_{i^{\prime }}\le b_{i^{\prime }}$, и на позицию позицию $x$ поставили число $x$.
2. $dp[0][x]$ для $a_0\le x\le b_0$ — первый член последовательности $c$.
3. Считаем двумя вложеными циклами — for (int i = 1; i < n; i++) for (int x = 0; x <= 3000; x++)

Новое состояние $dp[i][x]$ :

• ${\sum }_{y\le x}dp[i-1][y]$. (так как по условию $c_{i-1}\le c_i$) Если $a_i\le x\le b_i$.
• Иначе $0$, так как число $x$ просто не может стоять на позиции $i$.

4. Ответ — ${\sum }_{0\le x\le 3000}dp[n-1][x]$.

Такое решение работает за $O(n^3)$ ($x\approx n$ по условию задачи одинаковые размерности) — TL. Давайте немного соптимизируем. Точнее напишем немного умнее.

1. Можно хранить только два слоя, так как $dp[i][.]$ зависит только от значений $dp[i-1][.]$ => так красивее писать, и меньше памяти.
2. Сумма для вычисления $dp[i][x]$ немного отличается от $dp[i][x-1]$, а именно на значение $dp[i-1][x]$.

Вау??? Если честно я офигел от того, когда вспомнил такую задачу. Это просто замечательная задача. Два способа позволяют написать такой лаконичный код всего с одним измерением:

void solve() {
  int n;
  cin >> n;
  vector<int> a(n), b(n);
  for (int i = 0; i < n; i++) cin >> a[i];
  for (int i = 0; i < n; i++) cin >> b[i];

  vector<int> dp(3000 + 7);
  for (int i = a[0]; i <= b[0]; i++) dp[i] = 1;

  for (int i = 1; i < n; i++) {
    int sum = 0;
    for (int ci = 0; ci < dp.size(); ci++) {
      sum = add(sum, dp[ci]);
      if (a[i] <= ci && ci <= b[i])
        dp[ci] = sum;
      else
        dp[ci] = 0;
    }
  }
  int ans = 0;
  for (auto& x : dp) {
    ans = add(ans, x);
  }
  cout << ans;
}