Function to return a raised to the power n with complexity O ( log ( n ) )
def powmod ( a , n ) : NEW_LINE INDENT if not n : NEW_LINE INDENT return 1 NEW_LINE DEDENT pt = powmod ( a , n // 2 ) NEW_LINE pt = ( pt * pt ) % mod NEW_LINE if n % 2 : NEW_LINE INDENT return ( pt * a ) % mod NEW_LINE DEDENT else : NEW_LINE INDENT return pt NEW_LINE DEDENT DEDENT