Combinations

need some kind of ModInt. (as Z)

struct Combinations {
  int n;
  std::vector<Z> fact;
  std::vector<Z> ifact;

  Combinations() : n(1), fact(1, 1), ifact(1, 1) {
    void(0);
  }

  void ready(int m) {
    if (m < n) {
      return;
    }
    int new_n = std::max(2 * n, m + 1);
    fact.resize(new_n);
    for (int i = n; i < new_n; ++i) {
      fact[i] = i * fact[i - 1];
    }
    ifact.resize(new_n);
    ifact[new_n - 1] = 1 / fact[new_n - 1];
    for (int i = new_n - 2; i >= n; --i) {
      ifact[i] = (i + 1) * ifact[i + 1];
    }
    n = new_n;
  }

  Z fac(int x) {
    assert(x >= 0);
    ready(x);
    return fact[x];
  }

  Z ifac(int x) {
    assert(x >= 0);
    ready(x);
    return ifact[x];
  }

  Z inv(int x) {
    return fac(x - 1) * ifac(x);
  }

  Z C(int n, int r) {
    if (r < 0 || n < r) {
      return 0;
    }
    return fac(n) * ifac(r) * ifac(n - r);
  }

  Z P(int n, int r) {
    if (r < 0 || n < r) {
      return 0;
    }
    return fac(n) * ifac(n - r);
  }

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