Function to return base ^ exponent
def expo ( base , exponent ) : NEW_LINE INDENT ans = 1 NEW_LINE while ( exponent != 0 ) : NEW_LINE INDENT if ( ( exponent & 1 ) == 1 ) : NEW_LINE INDENT ans = ans * base NEW_LINE ans = ans % mod NEW_LINE DEDENT base = base * base NEW_LINE base %= mod NEW_LINE exponent >>= 1 NEW_LINE DEDENT return ans % mod NEW_LINE DEDENT