Function to find a ^ b modulo M
def modPower ( a , b , M ) : NEW_LINE INDENT res = 1 NEW_LINE while ( b ) : NEW_LINE INDENT if ( b & 1 ) : NEW_LINE INDENT res = res * a % M NEW_LINE DEDENT a = a * a % M NEW_LINE b >>= 1 NEW_LINE DEDENT return res NEW_LINE DEDENT