Inverse mod

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

    return b;
  }

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

  return gcd;
}

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