def modpow(k, n, m):
  """ Calculate "k^n" modular "m" efficiently.

  Even with python2 this is 100's of times faster than "(k**n) % m",
  particularly for large "n".

  Note however that python's built-in pow() also supports an optional 3rd
  modular argument and is faster than this.
  """
  ans = 1
  while n:
    if n & 1:
      ans = (ans*k) % m
    k = (k*k) % m
    n >>= 1
  return ans