Function to compute a ^ n % mod
def power ( a , n ) : NEW_LINE INDENT if ( n == 0 ) : NEW_LINE INDENT return 1 NEW_LINE DEDENT p = power ( a , int ( n / 2 ) ) % mod ; NEW_LINE p = ( p * p ) % mod NEW_LINE if ( n & 1 ) : NEW_LINE INDENT p = ( p * a ) % mod NEW_LINE DEDENT return p NEW_LINE DEDENT