Count Bounded Increasing Sequences (math/combinatorics/count-bounded-increasing-sequences.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2026-08-02 17:14:47+00:00
• Include: #include "math/combinatorics/count-bounded-increasing-sequences.hpp"

広義単調増加な整数列に上限が与えられたとき、条件を満たす列の個数を求めます。

count_bounded_increasing_sequences

template <typename Mint>
Mint count_bounded_increasing_sequences(
    const vector<int> &lower_bounds,
    const vector<int> &upper_bounds)

長さ $N$ の広義単調増加な整数列 $B$ であって、すべての $i$ について

\[\mathrm{lower\_bounds}_i \leq B_i \lt \mathrm{upper\_bounds}_i\]

を満たすものの個数を返します。空列の個数は $1$ とします。上下限は単調でなくても構いません。上限のみを指定したい場合は、lower_bounds のすべての要素を $0$ にします。

制約

• $0 \leq \mathrm{upper_bounds}_i$
• lower_bounds.size() == upper_bounds.size()
• $0 \leq \mathrm{lower_bounds}_i$
• Mint は NTT-friendly modint
• $N + U_{N-1} - L_0 + 6 \lt$ Mint::mod()

ここで、$L$ は下限の prefix max、$U$ は上限の suffix min とします。

計算量

$H=U_{N-1}-L_0$ とします。

• $O((N+H)\log^2(N+H))$

参考

• 上限付き単調増加列の数え上げ

Depends on

• Enumeration (組み合わせ) (math/combinatorics/enumeration.hpp)
• Number Theoretic Transform Friendly ModInt (math/fft/number-theoretic-transform-friendly-mod-int.hpp)

Verified with

• test/verify/yosupo-number-of-increasing-sequences-between-two-sequences.test.cpp

Code

#pragma once

#include "../fft/number-theoretic-transform-friendly-mod-int.hpp"
#include "enumeration.hpp"

/**
 * @brief Count Bounded Increasing Sequences
 */
template <typename Mint>
Mint count_bounded_increasing_sequences(const vector<int>& lower_bounds,
                                        const vector<int>& upper_bounds) {
  using NTT = NumberTheoreticTransformFriendlyModInt<Mint>;

  assert(lower_bounds.size() == upper_bounds.size());
  const int original_n = static_cast<int>(upper_bounds.size());
  if (original_n == 0) return Mint(1);

  vector<int> lower(lower_bounds), upper(upper_bounds);
  for (int i = 0; i < original_n; i++) {
    assert(lower[i] >= 0);
    assert(upper[i] >= 0);
    if (i > 0) lower[i] = max(lower[i], lower[i - 1]);
  }
  for (int i = original_n - 1; i-- > 0;) {
    upper[i] = min(upper[i], upper[i + 1]);
  }
  for (int i = 0; i < original_n; i++) {
    if (lower[i] >= upper[i]) return Mint(0);
    --upper[i];
  }

  // Shift the lower boundary one column to the right and translate by L[0].
  const int base = lower[0];
  const int n = original_n + 1;
  vector<int> lower_boundary(n), upper_boundary(n);
  lower_boundary[0] = 0;
  for (int i = 0; i < original_n; i++) {
    lower_boundary[i + 1] = lower[i] - base;
    upper_boundary[i] = upper[i] - base;
  }
  // A terminal vertical edge. The extra height does not change the answer.
  upper_boundary[original_n] = upper.back() - base + 1;

  const int max_factorial = n + upper_boundary.back() + 5;
  assert(static_cast<uint64_t>(max_factorial) < Mint::mod());
  Enumeration<Mint> enumeration(max_factorial);

  // Compute only the first `limit` coefficients.
  auto convolution_prefix = [&](vector<Mint> f, vector<Mint> g, int limit) {
    assert(limit >= 0);
    if (limit == 0) return vector<Mint>();
    assert(!f.empty() && !g.empty());
    if (static_cast<int>(f.size()) > limit) f.resize(limit);
    if (static_cast<int>(g.size()) > limit) g.resize(limit);

    if (min(f.size(), g.size()) <= 32) {
      vector<Mint> result(limit);
      for (int i = 0; i < static_cast<int>(f.size()); i++) {
        if (f[i] == Mint(0)) continue;
        const int m = min<int>(static_cast<int>(g.size()), limit - i);
        for (int j = 0; j < m; j++) result[i + j] += f[i] * g[j];
      }
      return result;
    }

    auto result = NTT::multiply(std::move(f), std::move(g));
    result.resize(limit);
    return result;
  };

  auto propagate_rectangle = [&](const vector<Mint>& left_edge,
                                 const vector<Mint>& bottom_edge) {
    const int height = static_cast<int>(left_edge.size());
    const int width = static_cast<int>(bottom_edge.size());
    assert(width > 0);
    if (height == 0) {
      return make_pair(bottom_edge, vector<Mint>());
    }

    vector<Mint> top_edge(width), right_edge(height);
    const bool has_left = any_of(left_edge.begin(), left_edge.end(),
                                 [](const Mint& x) { return x != Mint(0); });
    const bool has_bottom = any_of(bottom_edge.begin(), bottom_edge.end(),
                                   [](const Mint& x) { return x != Mint(0); });

    // Left -> top and bottom -> right are middle products with the same
    // factorial kernel. A cyclic convolution of length >= height + width - 1
    // computes the required middle coefficients without wraparound.
    if (has_left || has_bottom) {
      if (min(height, width) <= 32) {
        if (has_left) {
          vector<Mint> scaled(height);
          for (int k = 0; k < height; k++) {
            scaled[k] = left_edge[height - 1 - k] * enumeration.finv(k);
          }
          for (int j = 0; j < width; j++) {
            Mint sum = 0;
            for (int k = 0; k < height; k++) {
              sum += scaled[k] * enumeration.fact(j + k);
            }
            top_edge[j] += sum * enumeration.finv(j);
          }
        }
        if (has_bottom) {
          vector<Mint> scaled(width);
          for (int k = 0; k < width; k++) {
            scaled[k] = bottom_edge[width - 1 - k] * enumeration.finv(k);
          }
          for (int j = 0; j < height; j++) {
            Mint sum = 0;
            for (int k = 0; k < width; k++) {
              sum += scaled[k] * enumeration.fact(j + k);
            }
            right_edge[j] += sum * enumeration.finv(j);
          }
        }
      } else {
        int size = 1;
        while (size < height + width - 1) size <<= 1;

        vector<Mint> kernel(size);
        for (int i = 0; i < height + width - 1; i++) {
          kernel[i] = enumeration.fact(i);
        }
        NTT::ntt(kernel);

        // Fold the inverse-transform normalization into the shared kernel.
        const Mint inv_size = Mint(1) / Mint(size);
        for (auto& x : kernel) x *= inv_size;

        auto apply_middle_product = [&](const vector<Mint>& input,
                                        vector<Mint>& output) {
          const int input_size = static_cast<int>(input.size());
          vector<Mint> f(size);
          f[0] = input[input_size - 1];
          for (int k = 1; k < input_size; k++) {
            f[size - k] = input[input_size - 1 - k] * enumeration.finv(k);
          }
          NTT::ntt(f);
          for (int i = 0; i < size; i++) f[i] *= kernel[i];
          NTT::intt(f, false);
          for (int i = 0; i < static_cast<int>(output.size()); i++) {
            output[i] += f[i] * enumeration.finv(i);
          }
        };

        if (has_left) apply_middle_product(left_edge, top_edge);
        if (has_bottom) apply_middle_product(bottom_edge, right_edge);
      }
    }

    // Bottom -> top.
    if (has_bottom) {
      vector<Mint> kernel(width);
      for (int i = 0; i < width; i++) {
        kernel[i] = enumeration.fact(height - 1 + i) * enumeration.finv(i);
      }
      auto f = convolution_prefix(bottom_edge, std::move(kernel), width);
      const Mint coefficient = enumeration.finv(height - 1);
      for (int i = 0; i < width; i++) top_edge[i] += coefficient * f[i];
    }

    // Left -> right.
    if (has_left) {
      vector<Mint> kernel(height);
      for (int i = 0; i < height; i++) {
        kernel[i] = enumeration.fact(width - 1 + i) * enumeration.finv(i);
      }
      auto f = convolution_prefix(left_edge, std::move(kernel), height);
      const Mint coefficient = enumeration.finv(width - 1);
      for (int i = 0; i < height; i++) right_edge[i] += coefficient * f[i];
    }

    return make_pair(top_edge, right_edge);
  };

  // Solve a one-sided staircase. `heights` must be nondecreasing, and
  // `start[i]` is an additive source at the i-th bottom-edge vertex.
  auto solve_one_sided = [&](const vector<int>& heights,
                             const vector<Mint>& start) -> vector<Mint> {
    const int size = static_cast<int>(heights.size());
    assert(size > 0);
    assert(static_cast<int>(start.size()) == size);

    vector<int> bounds(size);
    for (int i = 0; i < size; i++) {
      assert(heights[i] >= 0);
      if (i > 0) assert(heights[i - 1] <= heights[i]);
      bounds[i] = heights[i] + 1;
    }

    auto rec = [&](auto& self, int l, int r, int bottom,
                   const vector<Mint>& bottom_edge) -> vector<Mint> {
      assert(static_cast<int>(bottom_edge.size()) == r - l);
      if (l + 1 == r) {
        return vector<Mint>(bounds[l] - bottom, bottom_edge[0]);
      }

      const int mid = (l + r) >> 1;
      const int height = bounds[mid] - bottom;

      auto left_edge = self(
          self, l, mid, bottom,
          vector<Mint>(bottom_edge.begin(), bottom_edge.begin() + mid - l));
      left_edge.resize(height);

      auto [top_edge, right_edge] = propagate_rectangle(
          left_edge,
          vector<Mint>(bottom_edge.begin() + mid - l, bottom_edge.end()));
      right_edge.resize(bounds[r - 1] - bottom);

      auto upper_right = self(self, mid, r, bounds[mid], top_edge);
      for (int i = 0; i < static_cast<int>(upper_right.size()); i++) {
        right_edge[height + i] += upper_right[i];
      }
      return right_edge;
    };

    return rec(rec, 0, size, 0, start);
  };

  // Decompose the corridor into alternating horizontal and vertical
  // one-sided staircases. Vertical pieces are transposed.
  const int distance = static_cast<int>(
      upper_bound(lower_boundary.begin(), lower_boundary.end(), 0) -
      lower_boundary.begin());
  int px = 0, py = 0;
  int qx = distance - 1, qy = 0;
  if (qx == 0) qy = upper_boundary[0];

  vector<Mint> current(abs(qx - px) + abs(qy - py) + 1);
  current[0] = Mint(1);
  bool first_piece = true;

  while (qx != n - 1 || qy != upper_boundary[n - 1]) {
    // Boundary DP values are prefix sums of additive sources.
    if (!first_piece) {
      for (int i = static_cast<int>(current.size()) - 1; i >= 1; i--) {
        current[i] -= current[i - 1];
      }
    }
    first_piece = false;

    if (py == qy) {
      vector<int> heights(qx - px + 1);
      for (int i = 0; i <= qx - px; i++) {
        heights[i] = upper_boundary[px + i] - py;
      }
      current = solve_one_sided(heights, std::move(current));
      px = qx;
      py = qy;
      qy = upper_boundary[qx];
    } else {
      // qx + 1 is the first lower-boundary index above py. The pointer moves
      // monotonically over this vertical segment.
      int x = qx + 1;
      const int base_x = x;
      vector<int> heights(qy - py + 1);
      for (int i = 0; i <= qy - py; i++) {
        const int y = py + i;
        while (x < n && lower_boundary[x] <= y) ++x;
        heights[i] = x - base_x;
      }
      current = solve_one_sided(heights, std::move(current));
      px = qx;
      py = qy;
      qx = x - 1;
    }
  }

  return current.back();
}

#line 2 "math/combinatorics/count-bounded-increasing-sequences.hpp"

#line 1 "math/fft/number-theoretic-transform-friendly-mod-int.hpp"
/**
 * @brief Number Theoretic Transform Friendly ModInt
 */
template <typename Mint>
struct NumberTheoreticTransformFriendlyModInt {
  static vector<Mint> roots, iroots, rate2, irate2, rate3, irate3;
  static int max_base;

  NumberTheoreticTransformFriendlyModInt() = default;

  static void init() {
    if (roots.empty()) {
      const unsigned mod = Mint::mod();
      assert(mod >= 3 && mod % 2 == 1);
      auto tmp = mod - 1;
      max_base = 0;
      while (tmp % 2 == 0) tmp >>= 1, max_base++;
      Mint root = 2;
      while (root.pow((mod - 1) >> 1) == 1) {
        root += 1;
      }
      assert(root.pow(mod - 1) == 1);

      roots.resize(max_base + 1);
      iroots.resize(max_base + 1);
      rate2.resize(max_base + 1);
      irate2.resize(max_base + 1);
      rate3.resize(max_base + 1);
      irate3.resize(max_base + 1);

      roots[max_base] = root.pow((mod - 1) >> max_base);
      iroots[max_base] = Mint(1) / roots[max_base];
      for (int i = max_base - 1; i >= 0; i--) {
        roots[i] = roots[i + 1] * roots[i + 1];
        iroots[i] = iroots[i + 1] * iroots[i + 1];
      }
      {
        Mint prod = 1, iprod = 1;
        for (int i = 0; i <= max_base - 2; i++) {
          rate2[i] = roots[i + 2] * prod;
          irate2[i] = iroots[i + 2] * iprod;
          prod *= iroots[i + 2];
          iprod *= roots[i + 2];
        }
      }
      {
        Mint prod = 1, iprod = 1;
        for (int i = 0; i <= max_base - 3; i++) {
          rate3[i] = roots[i + 3] * prod;
          irate3[i] = iroots[i + 3] * iprod;
          prod *= iroots[i + 3];
          iprod *= roots[i + 3];
        }
      }
    }
  }

  static void ntt(vector<Mint>& a) {
    init();
    const int n = (int)a.size();
    assert((n & (n - 1)) == 0);
    int h = __builtin_ctz(n);
    assert(h <= max_base);
    int len = 0;
    Mint imag = roots[2];
    if (h & 1) {
      int p = 1 << (h - 1);
      for (int i = 0; i < p; i++) {
        auto r = a[i + p];
        a[i + p] = a[i] - r;
        a[i] += r;
      }
      len++;
    }
    for (; len + 1 < h; len += 2) {
      int p = 1 << (h - len - 2);
      {  // s = 0
        for (int i = 0; i < p; i++) {
          auto a0 = a[i];
          auto a1 = a[i + p];
          auto a2 = a[i + 2 * p];
          auto a3 = a[i + 3 * p];
          auto a1na3imag = (a1 - a3) * imag;
          auto a0a2 = a0 + a2;
          auto a1a3 = a1 + a3;
          auto a0na2 = a0 - a2;
          a[i] = a0a2 + a1a3;
          a[i + 1 * p] = a0a2 - a1a3;
          a[i + 2 * p] = a0na2 + a1na3imag;
          a[i + 3 * p] = a0na2 - a1na3imag;
        }
      }
      Mint rot = rate3[0];
      for (int s = 1; s < (1 << len); s++) {
        int offset = s << (h - len);
        Mint rot2 = rot * rot;
        Mint rot3 = rot2 * rot;
        for (int i = 0; i < p; i++) {
          auto a0 = a[i + offset];
          auto a1 = a[i + offset + p] * rot;
          auto a2 = a[i + offset + 2 * p] * rot2;
          auto a3 = a[i + offset + 3 * p] * rot3;
          auto a1na3imag = (a1 - a3) * imag;
          auto a0a2 = a0 + a2;
          auto a1a3 = a1 + a3;
          auto a0na2 = a0 - a2;
          a[i + offset] = a0a2 + a1a3;
          a[i + offset + 1 * p] = a0a2 - a1a3;
          a[i + offset + 2 * p] = a0na2 + a1na3imag;
          a[i + offset + 3 * p] = a0na2 - a1na3imag;
        }
        rot *= rate3[__builtin_ctz(~s)];
      }
    }
  }

  static void intt(vector<Mint>& a, bool f = true) {
    init();
    const int n = (int)a.size();
    assert((n & (n - 1)) == 0);
    int h = __builtin_ctz(n);
    assert(h <= max_base);
    int len = h;
    Mint iimag = iroots[2];
    for (; len > 1; len -= 2) {
      int p = 1 << (h - len);
      {  // s = 0
        for (int i = 0; i < p; i++) {
          auto a0 = a[i];
          auto a1 = a[i + 1 * p];
          auto a2 = a[i + 2 * p];
          auto a3 = a[i + 3 * p];
          auto a2na3iimag = (a2 - a3) * iimag;
          auto a0na1 = a0 - a1;
          auto a0a1 = a0 + a1;
          auto a2a3 = a2 + a3;
          a[i] = a0a1 + a2a3;
          a[i + 1 * p] = (a0na1 + a2na3iimag);
          a[i + 2 * p] = (a0a1 - a2a3);
          a[i + 3 * p] = (a0na1 - a2na3iimag);
        }
      }
      Mint irot = irate3[0];
      for (int s = 1; s < (1 << (len - 2)); s++) {
        int offset = s << (h - len + 2);
        Mint irot2 = irot * irot;
        Mint irot3 = irot2 * irot;
        for (int i = 0; i < p; i++) {
          auto a0 = a[i + offset];
          auto a1 = a[i + offset + 1 * p];
          auto a2 = a[i + offset + 2 * p];
          auto a3 = a[i + offset + 3 * p];
          auto a2na3iimag = (a2 - a3) * iimag;
          auto a0na1 = a0 - a1;
          auto a0a1 = a0 + a1;
          auto a2a3 = a2 + a3;
          a[i + offset] = a0a1 + a2a3;
          a[i + offset + 1 * p] = (a0na1 + a2na3iimag) * irot;
          a[i + offset + 2 * p] = (a0a1 - a2a3) * irot2;
          a[i + offset + 3 * p] = (a0na1 - a2na3iimag) * irot3;
        }
        irot *= irate3[__builtin_ctz(~s)];
      }
    }
    if (len >= 1) {
      int p = 1 << (h - 1);
      for (int i = 0; i < p; i++) {
        auto ajp = a[i] - a[i + p];
        a[i] += a[i + p];
        a[i + p] = ajp;
      }
    }
    if (f) {
      Mint inv_sz = Mint(1) / n;
      for (int i = 0; i < n; i++) a[i] *= inv_sz;
    }
  }

  /**
   * @brief Transpose of ntt()
   */
  static void transposed_ntt(vector<Mint>& a) {
    init();
    const int n = (int)a.size();
    assert((n & (n - 1)) == 0);
    const int h = __builtin_ctz(n);
    assert(h <= max_base);

    int len = h;
    const Mint imag = roots[2];
    while (len > 0) {
      if (len == 1) {
        const int p = 1 << (h - len);
        Mint rot = 1;
        for (int s = 0; s < (1 << (len - 1)); s++) {
          const int offset = s << (h - len + 1);
          for (int i = 0; i < p; i++) {
            const auto lhs = a[i + offset];
            const auto rhs = a[i + offset + p];
            a[i + offset] = lhs + rhs;
            a[i + offset + p] = (lhs - rhs) * rot;
          }
          rot *= rate2[__builtin_ctz(~s)];
        }
        len--;
      } else {
        const int p = 1 << (h - len);
        Mint rot = 1;
        for (int s = 0; s < (1 << (len - 2)); s++) {
          const int offset = s << (h - len + 2);
          const Mint rot2 = rot * rot;
          const Mint rot3 = rot2 * rot;
          for (int i = 0; i < p; i++) {
            const auto a0 = a[i + offset];
            const auto a1 = a[i + offset + p];
            const auto a2 = a[i + offset + 2 * p];
            const auto a3 = a[i + offset + 3 * p];
            const auto x = (a2 - a3) * imag;
            a[i + offset] = a0 + a1 + a2 + a3;
            a[i + offset + p] = (a0 - a1 + x) * rot;
            a[i + offset + 2 * p] = (a0 + a1 - a2 - a3) * rot2;
            a[i + offset + 3 * p] = (a0 - a1 - x) * rot3;
          }
          rot *= rate3[__builtin_ctz(~s)];
        }
        len -= 2;
      }
    }
  }

  /**
   * @brief Transpose of intt()
   */
  static void transposed_intt(vector<Mint>& a, bool f = true) {
    init();
    const int n = (int)a.size();
    assert((n & (n - 1)) == 0);
    const int h = __builtin_ctz(n);
    assert(h <= max_base);

    if (f) {
      const Mint inv_sz = Mint(1) / n;
      for (auto& value : a) value *= inv_sz;
    }

    int len = 0;
    const Mint iimag = iroots[2];
    while (len < h) {
      if (len == h - 1) {
        const int p = 1 << (h - len - 1);
        Mint irot = 1;
        for (int s = 0; s < (1 << len); s++) {
          const int offset = s << (h - len);
          for (int i = 0; i < p; i++) {
            const auto lhs = a[i + offset];
            const auto rhs = a[i + offset + p] * irot;
            a[i + offset] = lhs + rhs;
            a[i + offset + p] = lhs - rhs;
          }
          irot *= irate2[__builtin_ctz(~s)];
        }
        len++;
      } else {
        const int p = 1 << (h - len - 2);
        Mint irot = 1;
        for (int s = 0; s < (1 << len); s++) {
          const Mint irot2 = irot * irot;
          const Mint irot3 = irot2 * irot;
          const int offset = s << (h - len);
          for (int i = 0; i < p; i++) {
            const auto a0 = a[i + offset];
            const auto a1 = a[i + offset + p] * irot;
            const auto a2 = a[i + offset + 2 * p] * irot2;
            const auto a3 = a[i + offset + 3 * p] * irot3;
            const auto x = (a1 - a3) * iimag;
            a[i + offset] = a0 + a2 + a1 + a3;
            a[i + offset + p] = a0 + a2 - a1 - a3;
            a[i + offset + 2 * p] = a0 - a2 + x;
            a[i + offset + 3 * p] = a0 - a2 - x;
          }
          irot *= irate3[__builtin_ctz(~s)];
        }
        len += 2;
      }
    }
  }

  static vector<Mint> multiply(vector<Mint> a, vector<Mint> b) {
    int need = a.size() + b.size() - 1;
    int nbase = 1;
    while ((1 << nbase) < need) nbase++;
    int sz = 1 << nbase;
    a.resize(sz, 0);
    b.resize(sz, 0);
    ntt(a);
    ntt(b);
    Mint inv_sz = Mint(1) / sz;
    for (int i = 0; i < sz; i++) a[i] *= b[i] * inv_sz;
    intt(a, false);
    a.resize(need);
    return a;
  }
};

template <typename Mint>
vector<Mint> NumberTheoreticTransformFriendlyModInt<Mint>::roots =
    vector<Mint>();
template <typename Mint>
vector<Mint> NumberTheoreticTransformFriendlyModInt<Mint>::iroots =
    vector<Mint>();
template <typename Mint>
vector<Mint> NumberTheoreticTransformFriendlyModInt<Mint>::rate2 =
    vector<Mint>();
template <typename Mint>
vector<Mint> NumberTheoreticTransformFriendlyModInt<Mint>::irate2 =
    vector<Mint>();
template <typename Mint>
vector<Mint> NumberTheoreticTransformFriendlyModInt<Mint>::rate3 =
    vector<Mint>();
template <typename Mint>
vector<Mint> NumberTheoreticTransformFriendlyModInt<Mint>::irate3 =
    vector<Mint>();
template <typename Mint>
int NumberTheoreticTransformFriendlyModInt<Mint>::max_base = 0;
#line 1 "math/combinatorics/enumeration.hpp"
/**
 * @brief Enumeration(組み合わせ)
 */
template <typename T>
struct Enumeration {
 private:
  static vector<T> _fact, _finv, _inv;

  inline static void expand(size_t sz) {
    if (_fact.size() < sz + 1) {
      int pre_sz = max(1, (int)_fact.size());
      _fact.resize(sz + 1, T(1));
      _finv.resize(sz + 1, T(1));
      _inv.resize(sz + 1, T(1));
      for (int i = pre_sz; i <= (int)sz; i++) {
        _fact[i] = _fact[i - 1] * T(i);
      }
      _finv[sz] = T(1) / _fact[sz];
      for (int i = (int)sz - 1; i >= pre_sz; i--) {
        _finv[i] = _finv[i + 1] * T(i + 1);
      }
      for (int i = pre_sz; i <= (int)sz; i++) {
        _inv[i] = _finv[i] * _fact[i - 1];
      }
    }
  }

 public:
  explicit Enumeration(size_t sz = 0) { expand(sz); }

  static inline T fact(int k) {
    expand(k);
    return _fact[k];
  }

  static inline T finv(int k) {
    expand(k);
    return _finv[k];
  }

  static inline T inv(int k) {
    expand(k);
    return _inv[k];
  }

  static T P(int n, int r) {
    if (r < 0 || n < r) return 0;
    return fact(n) * finv(n - r);
  }

  static T C(int p, int q) {
    if (q < 0 || p < q) return 0;
    return fact(p) * finv(q) * finv(p - q);
  }

  static T H(int n, int r) {
    if (n < 0 || r < 0) return 0;
    return r == 0 ? 1 : C(n + r - 1, r);
  }
};

template <typename T>
vector<T> Enumeration<T>::_fact = vector<T>();
template <typename T>
vector<T> Enumeration<T>::_finv = vector<T>();
template <typename T>
vector<T> Enumeration<T>::_inv = vector<T>();
#line 5 "math/combinatorics/count-bounded-increasing-sequences.hpp"

/**
 * @brief Count Bounded Increasing Sequences
 */
template <typename Mint>
Mint count_bounded_increasing_sequences(const vector<int>& lower_bounds,
                                        const vector<int>& upper_bounds) {
  using NTT = NumberTheoreticTransformFriendlyModInt<Mint>;

  assert(lower_bounds.size() == upper_bounds.size());
  const int original_n = static_cast<int>(upper_bounds.size());
  if (original_n == 0) return Mint(1);

  vector<int> lower(lower_bounds), upper(upper_bounds);
  for (int i = 0; i < original_n; i++) {
    assert(lower[i] >= 0);
    assert(upper[i] >= 0);
    if (i > 0) lower[i] = max(lower[i], lower[i - 1]);
  }
  for (int i = original_n - 1; i-- > 0;) {
    upper[i] = min(upper[i], upper[i + 1]);
  }
  for (int i = 0; i < original_n; i++) {
    if (lower[i] >= upper[i]) return Mint(0);
    --upper[i];
  }

  // Shift the lower boundary one column to the right and translate by L[0].
  const int base = lower[0];
  const int n = original_n + 1;
  vector<int> lower_boundary(n), upper_boundary(n);
  lower_boundary[0] = 0;
  for (int i = 0; i < original_n; i++) {
    lower_boundary[i + 1] = lower[i] - base;
    upper_boundary[i] = upper[i] - base;
  }
  // A terminal vertical edge. The extra height does not change the answer.
  upper_boundary[original_n] = upper.back() - base + 1;

  const int max_factorial = n + upper_boundary.back() + 5;
  assert(static_cast<uint64_t>(max_factorial) < Mint::mod());
  Enumeration<Mint> enumeration(max_factorial);

  // Compute only the first `limit` coefficients.
  auto convolution_prefix = [&](vector<Mint> f, vector<Mint> g, int limit) {
    assert(limit >= 0);
    if (limit == 0) return vector<Mint>();
    assert(!f.empty() && !g.empty());
    if (static_cast<int>(f.size()) > limit) f.resize(limit);
    if (static_cast<int>(g.size()) > limit) g.resize(limit);

    if (min(f.size(), g.size()) <= 32) {
      vector<Mint> result(limit);
      for (int i = 0; i < static_cast<int>(f.size()); i++) {
        if (f[i] == Mint(0)) continue;
        const int m = min<int>(static_cast<int>(g.size()), limit - i);
        for (int j = 0; j < m; j++) result[i + j] += f[i] * g[j];
      }
      return result;
    }

    auto result = NTT::multiply(std::move(f), std::move(g));
    result.resize(limit);
    return result;
  };

  auto propagate_rectangle = [&](const vector<Mint>& left_edge,
                                 const vector<Mint>& bottom_edge) {
    const int height = static_cast<int>(left_edge.size());
    const int width = static_cast<int>(bottom_edge.size());
    assert(width > 0);
    if (height == 0) {
      return make_pair(bottom_edge, vector<Mint>());
    }

    vector<Mint> top_edge(width), right_edge(height);
    const bool has_left = any_of(left_edge.begin(), left_edge.end(),
                                 [](const Mint& x) { return x != Mint(0); });
    const bool has_bottom = any_of(bottom_edge.begin(), bottom_edge.end(),
                                   [](const Mint& x) { return x != Mint(0); });

    // Left -> top and bottom -> right are middle products with the same
    // factorial kernel. A cyclic convolution of length >= height + width - 1
    // computes the required middle coefficients without wraparound.
    if (has_left || has_bottom) {
      if (min(height, width) <= 32) {
        if (has_left) {
          vector<Mint> scaled(height);
          for (int k = 0; k < height; k++) {
            scaled[k] = left_edge[height - 1 - k] * enumeration.finv(k);
          }
          for (int j = 0; j < width; j++) {
            Mint sum = 0;
            for (int k = 0; k < height; k++) {
              sum += scaled[k] * enumeration.fact(j + k);
            }
            top_edge[j] += sum * enumeration.finv(j);
          }
        }
        if (has_bottom) {
          vector<Mint> scaled(width);
          for (int k = 0; k < width; k++) {
            scaled[k] = bottom_edge[width - 1 - k] * enumeration.finv(k);
          }
          for (int j = 0; j < height; j++) {
            Mint sum = 0;
            for (int k = 0; k < width; k++) {
              sum += scaled[k] * enumeration.fact(j + k);
            }
            right_edge[j] += sum * enumeration.finv(j);
          }
        }
      } else {
        int size = 1;
        while (size < height + width - 1) size <<= 1;

        vector<Mint> kernel(size);
        for (int i = 0; i < height + width - 1; i++) {
          kernel[i] = enumeration.fact(i);
        }
        NTT::ntt(kernel);

        // Fold the inverse-transform normalization into the shared kernel.
        const Mint inv_size = Mint(1) / Mint(size);
        for (auto& x : kernel) x *= inv_size;

        auto apply_middle_product = [&](const vector<Mint>& input,
                                        vector<Mint>& output) {
          const int input_size = static_cast<int>(input.size());
          vector<Mint> f(size);
          f[0] = input[input_size - 1];
          for (int k = 1; k < input_size; k++) {
            f[size - k] = input[input_size - 1 - k] * enumeration.finv(k);
          }
          NTT::ntt(f);
          for (int i = 0; i < size; i++) f[i] *= kernel[i];
          NTT::intt(f, false);
          for (int i = 0; i < static_cast<int>(output.size()); i++) {
            output[i] += f[i] * enumeration.finv(i);
          }
        };

        if (has_left) apply_middle_product(left_edge, top_edge);
        if (has_bottom) apply_middle_product(bottom_edge, right_edge);
      }
    }

    // Bottom -> top.
    if (has_bottom) {
      vector<Mint> kernel(width);
      for (int i = 0; i < width; i++) {
        kernel[i] = enumeration.fact(height - 1 + i) * enumeration.finv(i);
      }
      auto f = convolution_prefix(bottom_edge, std::move(kernel), width);
      const Mint coefficient = enumeration.finv(height - 1);
      for (int i = 0; i < width; i++) top_edge[i] += coefficient * f[i];
    }

    // Left -> right.
    if (has_left) {
      vector<Mint> kernel(height);
      for (int i = 0; i < height; i++) {
        kernel[i] = enumeration.fact(width - 1 + i) * enumeration.finv(i);
      }
      auto f = convolution_prefix(left_edge, std::move(kernel), height);
      const Mint coefficient = enumeration.finv(width - 1);
      for (int i = 0; i < height; i++) right_edge[i] += coefficient * f[i];
    }

    return make_pair(top_edge, right_edge);
  };

  // Solve a one-sided staircase. `heights` must be nondecreasing, and
  // `start[i]` is an additive source at the i-th bottom-edge vertex.
  auto solve_one_sided = [&](const vector<int>& heights,
                             const vector<Mint>& start) -> vector<Mint> {
    const int size = static_cast<int>(heights.size());
    assert(size > 0);
    assert(static_cast<int>(start.size()) == size);

    vector<int> bounds(size);
    for (int i = 0; i < size; i++) {
      assert(heights[i] >= 0);
      if (i > 0) assert(heights[i - 1] <= heights[i]);
      bounds[i] = heights[i] + 1;
    }

    auto rec = [&](auto& self, int l, int r, int bottom,
                   const vector<Mint>& bottom_edge) -> vector<Mint> {
      assert(static_cast<int>(bottom_edge.size()) == r - l);
      if (l + 1 == r) {
        return vector<Mint>(bounds[l] - bottom, bottom_edge[0]);
      }

      const int mid = (l + r) >> 1;
      const int height = bounds[mid] - bottom;

      auto left_edge = self(
          self, l, mid, bottom,
          vector<Mint>(bottom_edge.begin(), bottom_edge.begin() + mid - l));
      left_edge.resize(height);

      auto [top_edge, right_edge] = propagate_rectangle(
          left_edge,
          vector<Mint>(bottom_edge.begin() + mid - l, bottom_edge.end()));
      right_edge.resize(bounds[r - 1] - bottom);

      auto upper_right = self(self, mid, r, bounds[mid], top_edge);
      for (int i = 0; i < static_cast<int>(upper_right.size()); i++) {
        right_edge[height + i] += upper_right[i];
      }
      return right_edge;
    };

    return rec(rec, 0, size, 0, start);
  };

  // Decompose the corridor into alternating horizontal and vertical
  // one-sided staircases. Vertical pieces are transposed.
  const int distance = static_cast<int>(
      upper_bound(lower_boundary.begin(), lower_boundary.end(), 0) -
      lower_boundary.begin());
  int px = 0, py = 0;
  int qx = distance - 1, qy = 0;
  if (qx == 0) qy = upper_boundary[0];

  vector<Mint> current(abs(qx - px) + abs(qy - py) + 1);
  current[0] = Mint(1);
  bool first_piece = true;

  while (qx != n - 1 || qy != upper_boundary[n - 1]) {
    // Boundary DP values are prefix sums of additive sources.
    if (!first_piece) {
      for (int i = static_cast<int>(current.size()) - 1; i >= 1; i--) {
        current[i] -= current[i - 1];
      }
    }
    first_piece = false;

    if (py == qy) {
      vector<int> heights(qx - px + 1);
      for (int i = 0; i <= qx - px; i++) {
        heights[i] = upper_boundary[px + i] - py;
      }
      current = solve_one_sided(heights, std::move(current));
      px = qx;
      py = qy;
      qy = upper_boundary[qx];
    } else {
      // qx + 1 is the first lower-boundary index above py. The pointer moves
      // monotonically over this vertical segment.
      int x = qx + 1;
      const int base_x = x;
      vector<int> heights(qy - py + 1);
      for (int i = 0; i <= qy - py; i++) {
        const int y = py + i;
        while (x < n && lower_boundary[x] <= y) ++x;
        heights[i] = x - base_x;
      }
      current = solve_one_sided(heights, std::move(current));
      px = qx;
      py = qy;
      qx = x - 1;
    }
  }

  return current.back();
}

Back to top page