Modular Inverse

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll extgcd(ll a, ll b, ll& x, ll& y) {
  if (!b) {
    x = 1;
    y = 0;
    return a;
  }
  ll x1, y1;
  ll g = extgcd(b, a % b, x1, y1);
  x = y1;
  y = x1 - (a / b) * y1;
  return g;
}

ll invFermat(ll a, ll mod) {
  ll res = 1, e = mod - 2;
  a %= mod;
  while (e > 0) {
    if (e & 1) {
      res = (__int128)res * a % mod;
    }
    a = (__int128)a * a % mod;
    e >>= 1;
  }
  return res;
}

ll invExtended(ll a, ll m) {
  ll x, y;
  ll g = extgcd(a, m, x, y);
  if (g != 1) {
    return -1;
  }
  return (x % m + m) % m;
}

vector<ll> invPrecompute(ll n, ll mod) {
  vector<ll> inv(n + 1);
  inv[1] = 1;
  for (ll i = 2; i <= n; i++)
    inv[i] = mod - (mod / i) % mod * inv[mod % i] % mod;
  return inv;
}