def mod_inverse(x, p):
  """Given 0 <= x < p, and p prime, returns y such that x * y % p == 1.

  >>> mod_inverse(2, 5)
  3
  >>> mod_inverse(3, 5)
  2
  >>> mod_inverse(3, 65537)
  21846
  """
  return pow(x, p - 2, p)