mod割り算の便利ツール（逆元、べき乗、階乗、二項係数nCr）

mod割り算まわりの便利ツールを用意したのでメモ これでmodに怯えずに戦える（かも）

modの演算の詳しい説明はけんちょんさんの以下の記事がとても分かりやすいです

qiita.com

便利ツール

// x!(mod mod)
ll mod_fact(ll x, ll mod) {
  ll ans = 1;
  for (int i = 2; i <= x; i++) {
    ans = (ans % mod) * i;
  }
  return ans % mod;
}

// a^n (mod mod)
ll modpow(ll a, ll n, ll mod) {
  ll ans = 1;
  while (n > 0) {
    if (n & 1) {
      ans = ans * a % mod;
    }
    a = a * a % mod;
    n >>= 1;
  }
  return ans;
}

// a^-1 (mod mod)
ll modinv(ll a, ll mod) { return modpow(a, mod - 2, mod); }

// nCr(mod mod)
ll mod_nCr(ll n, ll r, ll mod) {
  return mod_fact(n, mod) *
         modinv((mod_fact(r, mod) * mod_fact(n - r, mod)) % mod, mod) % mod;
}