def polynomial_exp_mod(base, exponent, polymod, p):
 assert (exponent < p)
 if (exponent == 0):
  return [1]
 G = base
 k = exponent
 if ((k % 2) == 1):
  s = G
 else:
  s = [1]
 while (k > 1):
  k = (k // 2)
  G = polynomial_multiply_mod(G, G, polymod, p)
  if ((k % 2) == 1):
   s = polynomial_multiply_mod(G, s, polymod, p)
 return s

def polynomial_exp_mod ( base , exponent , polymod , p ) : assert ( exponent < p ) if ( exponent == 0 ) : return [ 1 ] G = base k = exponent if ( ( k % 2 ) == 1 ) : s = G else : s = [ 1 ] while ( k > 1 ) : k = ( k // 2 ) G = polynomial_multiply_mod ( G , G , polymod , p ) if ( ( k % 2 ) == 1 ) : s = polynomial_multiply_mod ( G , s , polymod , p ) return s
polynomial exponentiation modulo a polynomial over ints mod p .