text: #pragma once
  #include <vector>
  #include "modulus/mint.hpp"
  
  template <int32_t MOD>
  mint<MOD> fact(int n) {
      static std::vector<mint<MOD> > memo(1, 1);
      while (n >= memo.size()) {
          memo.push_back(memo.back() * mint<MOD>(memo.size()));
      }
      return memo[n];
  }
  template <int32_t MOD>
  mint<MOD> inv_fact(int n) {
      static std::vector<mint<MOD> > memo;
      if (memo.size() <= n) {
          int l = memo.size();
          int r = n * 1.3 + 100;
          memo.resize(r);
          memo[r - 1] = fact<MOD>(r - 1).inv();
          for (int i = r - 2; i >= l; -- i) {
              memo[i] = memo[i + 1] * (i + 1);
          }
      }
      return memo[n];
  }
  