function to find moudulo inverse under 10 ^ 9 + 7
def modInv ( x ) : NEW_LINE INDENT n = MOD - 2 ; NEW_LINE result = 1 ; NEW_LINE while ( n ) : NEW_LINE INDENT if ( n & 1 ) : NEW_LINE INDENT result = result * x % MOD ; NEW_LINE DEDENT x = x * x % MOD ; NEW_LINE n = int ( n / 2 ) ; NEW_LINE DEDENT return result ; NEW_LINE DEDENT