Returns modulo exponentiation for two numbers represented as long long int . It is used by powerStrings ( ) . Its complexity is log ( n )
def powerLL ( x , n ) : NEW_LINE INDENT result = 1 ; NEW_LINE while ( n ) : NEW_LINE INDENT if ( n & 1 ) : NEW_LINE INDENT result = result * x % MOD ; NEW_LINE DEDENT n = int ( n / 2 ) ; NEW_LINE x = x * x % MOD ; NEW_LINE DEDENT return result ; NEW_LINE DEDENT