Inverse mod

ll gcd_extend(ll a, ll b, ll* x, ll* y) {
  if(a == 0) {
    *x = 0;
    *y = 1;

    return b;
  }

  ll gcd = gcd_extend(b % a, a, x, y);
  ll temp = *x;
  *x = *y - (b/a)*(*x);
  *y = temp;

  return gcd;
}

ll mod_inverse(ll a, ll mod) {
    ll res, tmp;
    gcd_extend(a, mod, &res, &tmp);
    while(res < 0) res += mod;
    return res;
}