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