Function to calculate and return x ^ n in log ( n ) time using Binary Exponentiation
def binExp ( base , power ) : NEW_LINE INDENT x = 1 NEW_LINE while ( power ) : NEW_LINE INDENT if ( power % 2 == 1 ) : NEW_LINE INDENT x = ( ( ( x % mod ) * ( base % mod ) ) % mod ) NEW_LINE DEDENT base = ( ( ( base % mod ) * ( base % mod ) ) % mod ) NEW_LINE power = power // 2 NEW_LINE DEDENT return x NEW_LINE DEDENT