Problem:


イヅア国語辞典

あなたはイヅア国の公用語であるイヅア語の国語辞典と、イヅア語のアルファベット（文字の一覧表）
を手に入れました。イヅア語のアルファベットにはN 種類の文字があります。イヅア語の国語辞典に現れる単語の順番は、イヅア語のアルファベット順に並んでいます。

辞典を見ると、載っているどの単語もN 文字で、しかも、N 種類の文字をひとつずつ含んでいることがわかりました。さらに調べてみると、辞典にはN 種類の文字の可能な並び方がすべて書かれていることを発見しました。

この発見から、あなたはある単語が辞典の何番目に出てくるかわかるようになりました。この知識を利用してイヅア国の人を驚かせてみましょう。まず、N 種類の文字をひとつずつアルファベット順に並べます。次に、任意の２文字の順番を入れ替える操作を R 回繰り返してもらいます。あなたは、出来上がった単語がイヅア国語辞典の何番目に出てくるか当てて見せます。そのための準備として、国語辞典中の単語の場所を求めるプログラムを作成してください。ただし、アルファベット順で最初の単語を 0 番目の単語とします。

入力

入力は複数のデータセットからなる。入力の終わりはゼロ１つの行で示される。各データセットは以下の形式で与えられる。

N
R
s1 t1
s2 t2
:
sR tR

１行目にアルファベットを構成する文字の数 N (1 ≤ N ≤ 100000) が与えられ、２行目に文字を入れ替えてもらう回数 R (0 ≤ R ≤ 50) が与えられる。続く R 行に、入れ替えられる文字の位置の組が与えられる。si と ti (1 ≤ si < ti ≤ N) は、先頭から数えて si 番目と ti 番目の文字を i 回目に入れ替えることを表す。si と ti は１つの空白で区切られている。

データセットの数は100 を超えない。

出力

データセットごとに、入れ替えが終わった時点で得られた単語が国語辞典の何番目に現れるかを示す数を１行に出力する。ただし、出力すべき値は非常に大きくなりうるので、代わりに 1,000,000,007 で割った余りを出力する。

入力例

3
2
1 2
2 3
4
2
2 3
2 4
0

出力例

3
4

入出力例の最初のデータセットについて説明する。説明のため、アルファベットは小さい方から順番に、'A', 'B', 'C' の３文字からなるとする。これらの文字をアルファベット順に並べると "ABC" という文字列が得られる。この文字列の１番目の文字 'A' と２番目の文字 'B' を入れ替えると、"BAC" という文字列が得られる。次に、得られた文字列の２番目の文字 'A' と３番目の文字 'C' を入れ替えると、単語 "BCA" が得られる。辞典には、先頭から順に "ABC", "ACB", "BAC", "BCA", "CAB", "CBA" の６種類の単語が載っている。"BCA" はこの中で３番目（最初の"ABC"が０番目であることに注意）に現れるので、3 を 1,000,000,007 で割った余りである 3 が答えになる。



Sample input:
3
2
1 2
2 3
4
2
2 3
2 4
0


Sample output:
3
4

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import math
import time
fact = []
tmp = 0
for i in xrange(100000):
	if i == 0:
		fact.append(1)
	else:
		fact.append(fact[i-1]*i%1000000007)
N = int(raw_input())
start = time.time()
while N != 0: 
	K = int(raw_input())
	data = [i for i in xrange(N)]
	index = list(data)
	input_lines = []
	for i in xrange(K):
		input_lines.append(raw_input())
		a,b = [int(x)-1 for x in input_lines[i].split(" ")]
		if(a+1 != b):
			for j in xrange(a+1,b):
				if(data[j]<data[a] and data[b]<data[j]):
					index[j] += 1
					index[a] += 1
				elif(data[a]<data[j] and data[j]<data[b]):
					index[j] -= 1
					index[b] -= 1
				elif(data[j]<data[a] and data[j]<data[b]):
					index[a] += 1
					index[b] -= 1		
		if(data[a]>data[b]):
			index[a] += 1
		elif(data[a]<data[b]):
			index[b] -= 1
		data[a],data[b] = data[b],data[a]
		index[a],index[b] = index[b],index[a]
	value = 0
	for i in xrange(N):
		value += (data[i] - index[i])*fact[N-1-i] % 1000000007
	print value % 1000000007
	elapsed_time = time.time() - start
	if(int(elapsed_time)>1):
		print 100
	N = int(raw_input())

Submission status: Wrong Answer

Solution code:
class BIT:
    MAX_IDX = 100001
    def __init__(self):
        self.bit = [0 for i in range(self.MAX_IDX+1)]

    def update(self,idx,v):
        while idx <= self.MAX_IDX:
            self.bit[idx] += v
            idx += idx & (-idx)
    def sum(self,idx):
        res = 0
        while idx > 0:
            res += self.bit[idx]
            idx -= idx & (-idx)
        return res
MAX_IDX = 100001
dp = [0 for i in range(MAX_IDX)]
dp[0] = 1

while 1:
    N = int(input())
    if N == 0:break

    bit = BIT()
    izua=[i for i in range(N+1)]
    for i in range(1,N+1):
        if dp[i] == 0:
            dp[i] = (dp[i-1]*i) % 1000000007 

    R = int(input())
    for i in range(R):#swap
        s,t = list(map(int,input().split()))
        w = izua[t]
        izua[t] = izua[s]
        izua[s] = w

    res = 0
    for i in range(N,0,-1):
        res += (bit.sum(izua[i])*dp[N-i]) % 1000000007 
        bit.update(izua[i],1)

    print (res)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
write = sys.stdout.write

def main():
    MOD = 10**9 + 7
    def query(k0):
        s = 0
        k = k0
        while k:
            s += data[k]
            k -= k & -k
        k = k0
        while k <= N:
            data[k] += 1
            k += k & -k
        return s % MOD

    L = 100000
    fact = [1]*(L+1)
    rfact = [1]*(L+1)
    r = 1
    for i in range(2, L+1):
        fact[i] = r = i * r % MOD
    rfact[i] = r = pow(fact[i], MOD-2, MOD)
    for i in range(L, 0, -1):
        rfact[i-1] = r = i * r % MOD

    while 1:
        N = int(readline())
        if N == 0:
            break
        R = int(readline())
        *S, = range(N)
        for i in range(R):
            s, t = map(int, readline().split()); s -= 1; t -= 1
            S[s], S[t] = S[t], S[s]
        data = [0]*(N+1)
        write("%d\n" % (sum(fact[N-1-i] * (e - query(e+1)) % MOD for i, e in enumerate(S)) % MOD))
main()

Submission status: Accepted

Solution code:
def solve():
    from sys import stdin
    m = 1000000007
    f_i = stdin
    
    while True:
        N = int(f_i.readline())
        if N == 0:
            break
        
        w = list(range(N))
        R = int(f_i.readline())
        for i in range(R):
            s, t = map(int, f_i.readline().split())
            s -= 1
            t -= 1
            w[s], w[t] = w[t], w[s]
        
        s = [(i, c) for i, c in enumerate(w) if i != c]
        s.sort(reverse=True)
        
        a = 1
        f = 1
        cnt = 0
        for c1, i in zip(w[::-1], range(N - 1, -1, -1)):
            if c1 > i:
                l = c1
                n = c1 - i - 1
            else:
                l = i
                n = 0
            for j, c2 in s:
                if j <= i:
                    break
                else:
                    if j < l:
                        n -= 1
                    if c2 < c1:
                        n += 1
            cnt = (cnt + (n * a) % m) % m
            a = (a * f) % m
            f += 1
        
        print(cnt)

solve()

Submission status: Runtime Error

Solution code:
# coding: utf-8
import math
N = int(raw_input())
while N != 0: 
	K = int(raw_input())
	data = []
	data2 = []
	#入れ替える前
	for i in range(N):
		data.append(i)
		data2.append(i)
	#入れ替えるところを抜き出し，入れ替える
	input_lines = []
	for i in range(K):
		input_lines.append(raw_input())
		a,b = [int(x)-1 for x in input_lines[i].split(" ")]
		#a番目とb番目を入れ替える
		data[a],data[b] = data[b],data[a]
	#探索
	k = 0
	value = 0
	for i in range(N-1):
		#tmpに格納されたdata[i]よりも小さい数の個数kを求める
		k = data[i] - data2.index(data[i])
		#if k != 0:
		value += (data[i]-k)*math.factorial(N-1-i)
		value = value % 1000000007
		data2.remove(data[i])
	print value
	N = int(raw_input())

Submission status: Runtime Error

Solution code:
# coding: utf-8
import math
N = int(raw_input())
while N != 0: 
	K = int(raw_input())
	data = []
	data2 = []
	#入れ替える前
	for i in range(N):
		data.append(i)
		data2.append(i)
	#入れ替えるところを抜き出し，入れ替える
	input_lines = []
	for i in range(K):
		input_lines.append(raw_input())
		a,b = [int(x)-1 for x in input_lines[i].split(" ")]
		#a番目とb番目を入れ替える
		data[a],data[b] = data[b],data[a]
	#探索
	k = 0
	value = 0
	for i in range(N-1):
		#tmpに格納されたdata[i]よりも小さい数の個数kを求める
		k = data[i] - data2.index(data[i])
		value += (data[i]-k)*math.factorial(N-1-i)
		value = value % 1000000007
		data2.remove(data[i])
	print value
	N = int(raw_input())

Submission status: Runtime Error

Solution code:
# coding: utf-8
import math
N = int(raw_input())
while N != 0: 
	K = int(raw_input())
	data = []
	data2 = []
	#入れ替える前
	for i in range(N):
		data.append(i)
		data2.append(i)
	#入れ替え
	input_lines = []
	for i in range(K):
		input_lines.append(raw_input())
		a,b = [int(x)-1 for x in input_lines[i].split(" ")]
		#a番目とb番目を入れ替える
		data[a],data[b] = data[b],data[a]
	#探索
	k = 0
	value = 0
	for i in range(N-1):
		#tmpに格納されたdata[i]よりも小さい数の個数kを求める
		k = data[i] - data2.index(data[i])
		value += (data[i]-k)*math.factorial(N-1-i)
		value = value % 1000000007
		data2.remove(data[i])
	print value
	N = int(raw_input())
	del data[:]
	del data2[:]
	del input_lines[:]

Submission status: Runtime Error

Solution code:
# coding: utf-8
import math
N = int(raw_input())
while N != 0: 
	K = int(raw_input())
	data = []
	data2 = []
	#入れ替える前
	for i in range(N):
		data.append(i)
		data2.append(i)
	#入れ替え
	input_lines = []
	for i in range(K):
		input_lines.append(raw_input())
		a,b = [int(x)-1 for x in input_lines[i].split(" ")]
		#a番目とb番目を入れ替える
		data[a],data[b] = data[b],data[a]
	#探索
	k = 0
	value = 0
	#階乗計算
	fact = []
	tmp = 0
	for i in range(N-1,-1,-1):
		if i == N-1:
			tmp = math.factorial(i)
			fact.insert(0,tmp)
		elif i == 0:
			fact.insert(0,1)
		else:
			tmp = tmp/(i+1)
			fact.insert(0,tmp)
	for i in range(N-1):
		#tmpに格納されたdata[i]よりも小さい数の個数kを求める
		k = data[i] - data2.index(data[i])
		value += (data[i]-k)*fact[N-1-i]
		value = value % 1000000007
		data2.remove(data[i])
	print value
	N = int(raw_input())

Submission status: Runtime Error

Solution code:
# coding: utf-8
import math
#階乗計算
fact = []
tmp = 0
for i in range(100000):
	if i == 0:
		fact.append(1)
	else:
		fact.append(fact[i-1]*i%1000000007)
N = int(raw_input())
while N != 0: 
	K = int(raw_input())
	data = []
	data2 = []
	#入れ替える前
	for i in range(N):
		data.append(i)
		data2.append(i)
	#入れ替え
	input_lines = []
	for i in range(K):
		input_lines.append(raw_input())
		a,b = [int(x)-1 for x in input_lines[i].split(" ")]
		#a番目とb番目を入れ替える
		data[a],data[b] = data[b],data[a]
	#探索
	k = 0
	value = 0
	for i in range(N-1):
		#tmpに格納されたdata[i]よりも小さい数の個数kを求める
		k = data[i] - data2.index(data[i])
		value += (data[i]-k)*fact[N-1-i]
		value = value % 1000000007
		data2.remove(data[i])
	print value
	N = int(raw_input())

Submission status: Runtime Error

Solution code:
# coding: utf-8
import math
#階乗計算
fact = []
tmp = 0
for i in range(100000):
	if i == 0:
		fact.append(1)
	else:
		fact.append(fact[i-1]*i%1000000007)
N = int(raw_input())
while N != 0: 
	K = int(raw_input())
	data = []
	data2 = []
	#入れ替える前
	for i in range(N):
		data.append(i)
		data2.append(i)
	#入れ替え
	input_lines = []
	for i in range(K):
		input_lines.append(raw_input())
		a,b = [int(x)-1 for x in input_lines[i].split(" ")]
		#a番目とb番目を入れ替える
		data[a],data[b] = data[b],data[a]
	#探索
	k = 0
	value = 0
	for i in range(N-1):
		#tmpに格納されたdata[i]よりも小さい数の個数kを求める
		k = data[i] - data2.index(data[i])
		value += (data[i]-k)*fact[N-1-i]
		value = value
		data2.remove(data[i])
	print value % 1000000007
	N = int(raw_input())

Submission status: Runtime Error

Solution code:
# coding: utf-8
import math
import scipy
#階乗計算
fact = []
tmp = 0
for i in range(100000):
	if i == 0:
		fact.append(1)
	else:
		fact.append(fact[i-1]*i%1000000007)
N = int(raw_input())
while N != 0: 
	K = int(raw_input())
	data = []
	data2 = []
	#入れ替える前
	for i in range(N):
		data.append(i)
		data2.append(i)
	#入れ替え
	input_lines = []
	for i in range(K):
		input_lines.append(raw_input())
		a,b = [int(x)-1 for x in input_lines[i].split(" ")]
		#a番目とb番目を入れ替える
		data[a],data[b] = data[b],data[a]
	#探索
	k = 0
	value = 0
	for i in range(N-1):
		#tmpに格納されたdata[i]よりも小さい数の個数kを求める
		k = data[i] - data2.index(data[i])
		value += (data[i]-k)*fact[N-1-i]
		value = value
		data2.remove(data[i])
	print value % 1000000007
	N = int(raw_input())

Submission status: Runtime Error

Solution code:
# coding: utf-8
import math
import numpy as np
#階乗計算
fact = []
tmp = 0
for i in range(100000):
	if i == 0:
		fact.append(1)
	else:
		fact.append(fact[i-1]*i%1000000007)
N = int(raw_input())
while N != 0: 
	K = int(raw_input())
	data = []
	data2 = []
	#入れ替える前
	for i in range(N):
		data.append(i)
		data2.append(i)
	#入れ替え
	input_lines = []
	for i in range(K):
		input_lines.append(raw_input())
		a,b = [int(x)-1 for x in input_lines[i].split(" ")]
		#a番目とb番目を入れ替える
		data[a],data[b] = data[b],data[a]
	#探索
	k = 0
	value = 0
	for i in range(N-1):
		#tmpに格納されたdata[i]よりも小さい数の個数kを求める
		k = data[i] - data2.index(data[i])
		value += (data[i]-k)*fact[N-1-i]
		value = value
		data2.remove(data[i])
	print value % 1000000007
	N = int(raw_input())

Submission status: Runtime Error

Solution code:
# coding: utf-8
import scipy
#階乗計算
fact = []
tmp = 0
for i in range(100000):
	if i == 0:
		fact.append(1)
	else:
		fact.append(fact[i-1]*i%1000000007)
N = int(raw_input())
while N != 0: 
	K = int(raw_input())
	data = []
	data2 = []
	#入れ替える前
	for i in range(N):
		data.append(i)
		data2.append(i)
	#入れ替え
	input_lines = []
	for i in range(K):
		input_lines.append(raw_input())
		a,b = [int(x)-1 for x in input_lines[i].split(" ")]
		#a番目とb番目を入れ替える
		data[a],data[b] = data[b],data[a]
	#探索
	k = 0
	value = 0
	for i in range(N-1):
		#tmpに格納されたdata[i]よりも小さい数の個数kを求める
		k = data[i] - data2.index(data[i])
		value += (data[i]-k)*fact[N-1-i]
		value = value % 1000000007
		data2.remove(data[i])
	print value 
	N = int(raw_input())

Submission status: Runtime Error

Solution code:
# coding: utf-8
import math
#階乗計算
fact = []
tmp = 0
for i in range(100000):
	if i == 0:
		fact.append(1)
	else:
		fact.append(fact[i-1]*i%1000000007)
N = int(raw_input())
while N != 0: 
	K = int(raw_input())
	data = []
	data2 = []
	#入れ替える前
	for i in range(N):
		data.append(i)
		data2.append(i)
	#入れ替え
	input_lines = []
	for i in range(K):
		input_lines.append(raw_input())
		a,b = [int(x)-1 for x in input_lines[i].split(" ")]
		#a番目とb番目を入れ替える
		data[a],data[b] = data[b],data[a]
	#探索
	k = 0
	value = 0
	for i in range(N-1):
		#tmpに格納されたdata[i]よりも小さい数の個数kを求める
		k = data[i] - data2.index(data[i])
		value += (data[i]-k)*fact[N-1-i]
		value = value % 1000000007
		data2.remove(data[i])
	print value 
	N = int(raw_input())

Submission status: Runtime Error

Solution code:
# coding: utf-8
import math
fact = []
tmp = 0
for i in range(100000):
	if i == 0:
		fact.append(1)
	else:
		fact.append(fact[i-1]*i%1000000007)
N = int(raw_input())
while N != 0: 
	K = int(raw_input())
	data = []
	index = []
	for i in range(N):
		data.append(i)
		index.append(i)
	input_lines = []
	for i in range(K):
		input_lines.append(raw_input())
		a,b = [int(x)-1 for x in input_lines[i].split(" ")]
		if(a+1 != b):
			for j in range(a+1,b):
				if(data[j]<data[a] and data[b]<data[j]):
					index[j] += 1
					index[a] += 1
				elif(data[a]<data[j] and data[j]<data[b]):
					index[j] -= 1
					index[b] -= 1
				elif(data[j]<data[a] and data[j]<data[b]):
					index[a] += 1
					index[b] -= 1		
		if(data[a]>data[b]):
			index[a] += 1
		elif(data[a]<data[b]):
			index[b] -= 1
		data[a],data[b] = data[b],data[a]
		index[a],index[b] = index[b],index[a]
	value = 0
	for i in range(N):
		value += (data[i] - index[i])*fact[N-1-i]
	print value% 1000000007
	N = int(raw_input())

Submission status: Runtime Error

Solution code:
# coding: utf-8
import math
fact = []
tmp = 0
for i in range(100000):
	if i == 0:
		fact.append(1)
	else:
		fact.append(fact[i-1]*i%1000000007)
N = int(raw_input())
while N != 0: 
	K = int(raw_input())
	data = []
	index = []
	for i in range(N):
		data.append(i)
		index.append(i)
	input_lines = []
	for i in range(K):
		input_lines.append(raw_input())
		a,b = [int(x)-1 for x in input_lines[i].split(" ")]
		if(a+1 != b):
			for j in range(a+1,b):
				if(data[j]<data[a] and data[b]<data[j]):
					index[j] += 1
					index[a] += 1
				elif(data[a]<data[j] and data[j]<data[b]):
					index[j] -= 1
					index[b] -= 1
				elif(data[j]<data[a] and data[j]<data[b]):
					index[a] += 1
					index[b] -= 1		
		if(data[a]>data[b]):
			index[a] += 1
		elif(data[a]<data[b]):
			index[b] -= 1
		data[a],data[b] = data[b],data[a]
		index[a],index[b] = index[b],index[a]
	value = 0
	for i in range(N):
		value += (data[i] - index[i])*fact[N-1-i]% 1000000007
	print value% 1000000007
	N = int(raw_input())

Submission status: Runtime Error

Solution code:
# coding: utf-8
import math
fact = []
tmp = 0
for i in range(100000):
	if i == 0:
		fact.append(1)
	else:
		fact.append(fact[i-1]*i%1000000007)
N = int(raw_input())
while N != 0: 
	K = int(raw_input())
	data = [i for i in range(N)]
	index = list(data)
	input_lines = []
	for i in range(K):
		input_lines.append(raw_input())
		a,b = [int(x)-1 for x in input_lines[i].split(" ")]
		if(a+1 != b):
			for j in range(a+1,b):
				if(data[j]<data[a] and data[b]<data[j]):
					index[j] += 1
					index[a] += 1
				elif(data[a]<data[j] and data[j]<data[b]):
					index[j] -= 1
					index[b] -= 1
				elif(data[j]<data[a] and data[j]<data[b]):
					index[a] += 1
					index[b] -= 1		
		if(data[a]>data[b]):
			index[a] += 1
		elif(data[a]<data[b]):
			index[b] -= 1
		data[a],data[b] = data[b],data[a]
		index[a],index[b] = index[b],index[a]
	value = 0
	for i in range(N):
		value += (data[i] - index[i])*fact[N-1-i]
	print value% 1000000007
	N = int(raw_input())

Submission status: Runtime Error

Solution code:
# coding: utf-8
import math
fact = []
tmp = 0
for i in range(100000):
	if i == 0:
		fact.append(1)
	else:
		fact.append(fact[i-1]*i%1000000007)
N = int(raw_input())
data_tmp = [i for i in range(N)]
while N != 0: 
	K = int(raw_input())
	data = list(data_tmp)
	index = list(data_tmp)
	input_lines = []
	for i in range(K):
		input_lines.append(raw_input())
		a,b = [int(x)-1 for x in input_lines[i].split(" ")]
		if(a+1 != b):
			for j in range(a+1,b):
				if(data[j]<data[a] and data[b]<data[j]):
					index[j] += 1
					index[a] += 1
				elif(data[a]<data[j] and data[j]<data[b]):
					index[j] -= 1
					index[b] -= 1
				elif(data[j]<data[a] and data[j]<data[b]):
					index[a] += 1
					index[b] -= 1		
		if(data[a]>data[b]):
			index[a] += 1
		elif(data[a]<data[b]):
			index[b] -= 1
		data[a],data[b] = data[b],data[a]
		index[a],index[b] = index[b],index[a]
	value = 0
	for i in range(N):
		value += (data[i] - index[i])*fact[N-1-i]
	print value% 1000000007
	N = int(raw_input())

Submission status: Runtime Error

Solution code:
# coding: utf-8
import math
fact = []
tmp = 0
for i in range(100000):
	if i == 0:
		fact.append(1)
	else:
		fact.append(fact[i-1]*i%1000000007)
N = long(raw_input())
while N != 0: 
	K = long(raw_input())
	data = [i for i in range(N)]
	index = list(data_tmp)
	input_lines = []
	for i in range(K):
		input_lines.append(raw_input())
		a,b = [long(x)-1 for x in input_lines[i].split(" ")]
		if(a+1 != b):
			for j in range(a+1,b):
				if(data[j]<data[a] and data[b]<data[j]):
					index[j] += 1
					index[a] += 1
				elif(data[a]<data[j] and data[j]<data[b]):
					index[j] -= 1
					index[b] -= 1
				elif(data[j]<data[a] and data[j]<data[b]):
					index[a] += 1
					index[b] -= 1		
		if(data[a]>data[b]):
			index[a] += 1
		elif(data[a]<data[b]):
			index[b] -= 1
		data[a],data[b] = data[b],data[a]
		index[a],index[b] = index[b],index[a]
	value = 0
	for i in range(N):
		value += (data[i] - index[i])*fact[N-1-i]
	print value% 1000000007
	N = long(raw_input())

Submission status: Runtime Error

Solution code:
# coding: utf-8
import math
fact = []
tmp = 0
for i in range(100000):
	if i == 0:
		fact.append(1)
	else:
		fact.append(fact[i-1]*i%1000000007)
N = long(raw_input())
while N != 0: 
	K = long(raw_input())
	data = [i for i in range(N)]
	index = list(data)
	input_lines = []
	for i in range(K):
		input_lines.append(raw_input())
		a,b = [long(x)-1 for x in input_lines[i].split(" ")]
		if(a+1 != b):
			for j in range(a+1,b):
				if(data[j]<data[a] and data[b]<data[j]):
					index[j] += 1
					index[a] += 1
				elif(data[a]<data[j] and data[j]<data[b]):
					index[j] -= 1
					index[b] -= 1
				elif(data[j]<data[a] and data[j]<data[b]):
					index[a] += 1
					index[b] -= 1		
		if(data[a]>data[b]):
			index[a] += 1
		elif(data[a]<data[b]):
			index[b] -= 1
		data[a],data[b] = data[b],data[a]
		index[a],index[b] = index[b],index[a]
	value = 0
	for i in range(N):
		value += (data[i] - index[i])*fact[N-1-i]
	print value% 1000000007
	N = long(raw_input())

Submission status: Runtime Error

Solution code:
# coding: utf-8
import math
fact = []
tmp = 0
for i in range(100000):
	if i == 0:
		fact.append(1)
	else:
		fact.append(fact[i-1]*i%1000000007)
N = int(raw_input())
while N != 0: 
	K = int(raw_input())
	data = [i for i in range(N)]
	index = list(data)
	input_lines = []
	for i in range(K):
		input_lines.append(raw_input())
		a,b = [int(x)-1 for x in input_lines[i].split(" ")]
		if(a+1 != b):
			for j in range(a+1,b):
				if(data[j]<data[a] and data[b]<data[j]):
					index[j] += 1
					index[a] += 1
				elif(data[a]<data[j] and data[j]<data[b]):
					index[j] -= 1
					index[b] -= 1
				elif(data[j]<data[a] and data[j]<data[b]):
					index[a] += 1
					index[b] -= 1		
		if(data[a]>data[b]):
			index[a] += 1
		elif(data[a]<data[b]):
			index[b] -= 1
		data[a],data[b] = data[b],data[a]
		index[a],index[b] = index[b],index[a]
	value = 0
	for i in range(N):
		value += (data[i] - index[i])*fact[N-1-i]% 1000000007
	print value % 1000000007
	N = int(raw_input())

Submission status: Runtime Error

Solution code:
# coding: utf-8
import math
fact = []
tmp = 0
for i in range(100000):
	if i == 0:
		fact.append(1)
	else:
		fact.append(fact[i-1]*i%1000000007)
N = int(raw_input())
while N != 0: 
	K = int(raw_input())
	data = [i for i in range(N)]
	index = list(data)
	input_lines = []
	for i in range(K):
		input_lines.append(raw_input())
		a,b = [int(x) for x in input_lines[i].split(" ")]
		a -= 1
		b -= 1
		if(a+1 != b):
			for j in range(a+1,b):
				if(data[j]<data[a] and data[b]<data[j]):
					index[j] += 1
					index[a] += 1
				elif(data[a]<data[j] and data[j]<data[b]):
					index[j] -= 1
					index[b] -= 1
				elif(data[j]<data[a] and data[j]<data[b]):
					index[a] += 1
					index[b] -= 1		
		if(data[a]>data[b]):
			index[a] += 1
		elif(data[a]<data[b]):
			index[b] -= 1
		data[a],data[b] = data[b],data[a]
		index[a],index[b] = index[b],index[a]
	value = 0
	for i in range(N):
		value += (data[i] - index[i])*fact[N-1-i] % 1000000007
	print value % 1000000007
	N = int(raw_input())

Submission status: Runtime Error

Solution code:
# coding: utf-8
import math
fact = []
tmp = 0
for i in xrange(100000):
	if i == 0:
		fact.append(1)
	else:
		fact.append(fact[i-1]*i%1000000007)
N = int(raw_input())
while N != 0: 
	K = int(raw_input())
	data = [i for i in xrange(N)]
	index = list(data)
	input_lines = []
	for i in xrange(K):
		input_lines.append(raw_input())
		a,b = [int(x)-1 for x in input_lines[i].split(" ")]
		if(a+1 != b):
			for j in xrange(a+1,b):
				if(data[j]<data[a] and data[b]<data[j]):
					index[j] += 1
					index[a] += 1
				elif(data[a]<data[j] and data[j]<data[b]):
					index[j] -= 1
					index[b] -= 1
				elif(data[j]<data[a] and data[j]<data[b]):
					index[a] += 1
					index[b] -= 1		
		if(data[a]>data[b]):
			index[a] += 1
		elif(data[a]<data[b]):
			index[b] -= 1
		data[a],data[b] = data[b],data[a]
		index[a],index[b] = index[b],index[a]
	value = 0
	for i in xrange(N):
		value += (data[i] - index[i])*fact[N-1-i] % 1000000007
	print value % 1000000007
	N = int(raw_input())

Submission status: Runtime Error

Solution code:
# coding: utf-8
import math
import time
fact = []
tmp = 0
for i in xrange(100000):
	if i == 0:
		fact.append(1)
	else:
		fact.append(fact[i-1]*i%1000000007)
N = int(raw_input())
start = time.time()
while N != 0: 
	K = int(raw_input())
	data = [i for i in xrange(N)]
	index = list(data)
	input_lines = []
	for i in xrange(K):
		input_lines.append(raw_input())
		a,b = [int(x)-1 for x in input_lines[i].split(" ")]
		if(a+1 != b):
			for j in xrange(a+1,b):
				if(data[j]<data[a] and data[b]<data[j]):
					index[j] += 1
					index[a] += 1
				elif(data[a]<data[j] and data[j]<data[b]):
					index[j] -= 1
					index[b] -= 1
				elif(data[j]<data[a] and data[j]<data[b]):
					index[a] += 1
					index[b] -= 1		
		if(data[a]>data[b]):
			index[a] += 1
		elif(data[a]<data[b]):
			index[b] -= 1
		data[a],data[b] = data[b],data[a]
		index[a],index[b] = index[b],index[a]
	value = 0
	for i in xrange(N):
		value += (data[i] - index[i])*fact[N-1-i] % 1000000007
	print value % 1000000007
	elapsed_time = time.time() - start
	if(int(elapsed_time)>40):
		print 100
	N = int(raw_input())

Submission status: Runtime Error

Solution code:
# coding: utf-8
import math
import time
fact = []
tmp = 0
for i in xrange(100000):
	if i == 0:
		fact.append(1)
	else:
		fact.append(fact[i-1]*i%1000000007)
N = int(raw_input())
start = time.time()
while N != 0: 
	K = int(raw_input())
	data = [i for i in xrange(N)]
	index = list(data)
	input_lines = []
	for i in xrange(K):
		input_lines.append(raw_input())
		a,b = [int(x)-1 for x in input_lines[i].split(" ")]
		if(a+1 != b):
			for j in xrange(a+1,b):
				if(data[j]<data[a] and data[b]<data[j]):
					index[j] += 1
					index[a] += 1
				elif(data[a]<data[j] and data[j]<data[b]):
					index[j] -= 1
					index[b] -= 1
				elif(data[j]<data[a] and data[j]<data[b]):
					index[a] += 1
					index[b] -= 1		
		if(data[a]>data[b]):
			index[a] += 1
		elif(data[a]<data[b]):
			index[b] -= 1
		data[a],data[b] = data[b],data[a]
		index[a],index[b] = index[b],index[a]
	value = 0
	for i in xrange(N):
		value += (data[i] - index[i])*fact[N-1-i] % 1000000007
	print value % 1000000007
	elapsed_time = time.time() - start
	if(int(elapsed_time)>10):
		print 100
	N = int(raw_input())

Submission status: Runtime Error

Solution code:
# coding: utf-8
import math
import time
fact = []
tmp = 0
for i in xrange(100000):
	if i == 0:
		fact.append(1)
	else:
		fact.append(fact[i-1]*i%1000000007)
N = int(raw_input())
start = time.time()
while N != 0: 
	K = int(raw_input())
	data = [i for i in xrange(N)]
	index = list(data)
	input_lines = []
	for i in xrange(K):
		input_lines.append(raw_input())
		a,b = [int(x)-1 for x in input_lines[i].split(" ")]
		if(a+1 != b):
			for j in xrange(a+1,b):
				if(data[j]<data[a] and data[b]<data[j]):
					index[j] += 1
					index[a] += 1
				elif(data[a]<data[j] and data[j]<data[b]):
					index[j] -= 1
					index[b] -= 1
				elif(data[j]<data[a] and data[j]<data[b]):
					index[a] += 1
					index[b] -= 1		
		if(data[a]>data[b]):
			index[a] += 1
		elif(data[a]<data[b]):
			index[b] -= 1
		data[a],data[b] = data[b],data[a]

Submission status: Runtime Error

Solution code:
# coding: utf-8
import math
import time
fact = []
tmp = 0
for i in xrange(100000):
	if i == 0:
		fact.append(1)
	else:
		fact.append(fact[i-1]*i%1000000007)
N = int(raw_input())
start = time.time()
while N != 0: 
	K = int(raw_input())
	data = [i for i in xrange(N)]
	index = list(data)
	input_lines = []
	for i in xrange(K):
		input_lines.append(raw_input())
		a,b = [int(x)-1 for x in input_lines[i].split(" ")]
		if(a+1 != b):
			for j in xrange(a+1,b):
				if(data[j]<data[a] and data[b]<data[j]):
					index[j] += 1
					index[a] += 1
				elif(data[a]<data[j] and data[j]<data[b]):
					index[j] -= 1
					index[b] -= 1
				elif(data[j]<data[a] and data[j]<data[b]):
					index[a] += 1
					index[b] -= 1		
		if(data[a]>data[b]):
			index[a] += 1
		elif(data[a]<data[b]):
			index[b] -= 1
		data[a],data[b] = data[b],data[a]
		index[a],index[b] = index[b],index[a]
	value = 0
	for i in xrange(N):
		value += (data[i] - index[i])*fact[N-1-i] % 1000000007
	print value % 1000000007
	elapsed_time = time.time() - start
	if(int(elapsed_time)>4):
		print 100
	N = int(raw_input())

Submission status: Runtime Error

Solution code:
# coding: utf-8
import math
fact = []
tmp = 0
for i in xrange(100000):
	if i == 0:
		fact.append(1)
	else:
		fact.append(fact[i-1]*i%1000000007)
N = int(raw_input())
while N != 0: 
	K = int(raw_input())
	data = [i for i in xrange(N)]
	index = list(data)
	input_lines = []
	for i in xrange(K):
		input_lines.append(raw_input())
		a,b = [int(x)-1 for x in input_lines[i].split(" ")]
		if(a+1 != b):
			for j in xrange(a+1,b):
				if(data[j]<data[a] and data[b]<data[j]):
					index[j] += 1
					index[a] += 1
				elif(data[a]<data[j] and data[j]<data[b]):
					index[j] -= 1
					index[b] -= 1
				elif(data[j]<data[a] and data[j]<data[b]):
					index[a] += 1
					index[b] -= 1		
		if(data[a]>data[b]):
			index[a] += 1
		elif(data[a]<data[b]):
			index[b] -= 1
		data[a],data[b] = data[b],data[a]
		index[a],index[b] = index[b],index[a]
	value = 0
	for i in xrange(N):
		value += (data[i] - index[i])*fact[N-1-i] % 1000000007
	print (value % 1000000007)
	N = int(raw_input())

Submission status: Runtime Error

Solution code:
# coding: utf-8
import math
fact = []
tmp = 0
for i in range(100000):
	if i == 0:
		fact.append(1)
	else:
		fact.append(fact[i-1]*i%1000000007)
N = int(input())
while N != 0: 
	K = int(input())
	data = [i for i in range(N)]
	index = list(data)
	input_lines = []
	for i in range(K):
		input_lines.append(input())
		a,b = [int(x)-1 for x in input_lines[i].split(" ")]
		if(a+1 != b):
			for j in range(a+1,b):
				if(data[j]<data[a] and data[b]<data[j]):
					index[j] += 1
					index[a] += 1
				elif(data[a]<data[j] and data[j]<data[b]):
					index[j] -= 1
					index[b] -= 1
				elif(data[j]<data[a] and data[j]<data[b]):
					index[a] += 1
					index[b] -= 1		
		if(data[a]>data[b]):
			index[a] += 1
		elif(data[a]<data[b]):
			index[b] -= 1
		data[a],data[b] = data[b],data[a]
		index[a],index[b] = index[b],index[a]
	value = 0
	for i in range(N):
		value += (data[i] - index[i])*fact[N-1-i] % 1000000007
	print (value % 1000000007)
	N = int(input())

Submission status: Runtime Error

Solution code:
class BIT:
    MAX_IDX = 100001
    def __init__(self):
        self.bit = [0 for i in range(self.MAX_IDX+1)]

    def update(self,idx,v):
        while idx <= self.MAX_IDX:
            self.bit[idx] += v
            idx += idx & (-idx)
    def sum(self,idx):
        res = 0
        while idx > 0:
            res += self.bit[idx]
            idx -= idx & (-idx)
        return res
MAX_IDX = 100001
dp = [0 for i in range(MAX_IDX)]
dp[0] = 1

while 1:
    N = int(input())
    if N == 0:break

    bit = BIT()
    izua=[i for i in range(N+1)]
    for i in range(1,N+1):
        if dp[i] == 0:
            dp[i] = (dp[i-1]*i) #% 1000000007 

    R = int(input())
    for i in range(R):#swap
        s,t = list(map(int,input().split()))
        w = izua[t]
        izua[t] = izua[s]
        izua[s] = w

    res = 0
    for i in range(N,0,-1):
        res += (bit.sum(izua[i])*dp[N-i]) % 1000000007 
        bit.update(izua[i],1)

    print (res)

Submission status: Runtime Error

Solution code:
class BIT:
    MAX_IDX = 100001
    def __init__(self):
        self.bit = [0 for i in range(self.MAX_IDX+1)]

    def update(self,idx,v):
        while idx <= self.MAX_IDX:
            self.bit[idx] += v
            idx += idx & (-idx)
    def sum(self,idx):
        res = 0
        while idx > 0:
            res += self.bit[idx]
            idx -= idx & (-idx)
        return res
MAX_IDX = 100001
MOD_V = 1000000007
dp = [0 for i in range(MAX_IDX)]
dp[0] = 1

while 1:
    N = int(input())
    if N == 0:break

    bit = BIT()
    izua=[i for i in range(N+1)]
    for i in range(1,N+1):
        if dp[i] == 0:
            dp[i] = (dp[i-1]*i) % MOD_V

    R = int(input())
    for i in range(R):#swap
        s,t = list(map(int,input().split()))
        w = izua[t]
        izua[t] = izua[s]
        izua[s] = w

    res = 0
    for i in range(N,0,-1):
        res += (bit.sum(izua[i])*dp[N-i]) % MOD_V 
        bit.update(izua[i],1)

    print (res%MOD_V)

Submission status: Runtime Error

Solution code:
class BIT:
    def __init__(self,size):
        self.bit = [0 for i in range(size+1)]

    def update(self,idx,v):
        while idx <= len(self.bit)-1:
            self.bit[idx] += v
            idx += idx & (-idx)
    def sum(self,idx):
        res = 0
        while idx > 0:
            res += self.bit[idx]
            idx -= idx & (-idx)
        return res
MOD_V = 1000000007

while 1:
    N = int(input())
    if N == 0:break
    dp = [0 for i in range(N+1)]
    dp[0] = 1

    bit = BIT(N)
    izua=[i for i in range(N+1)]
    for i in range(1,N+1):
        if dp[i] == 0:
            dp[i] = (dp[i-1]*i) % MOD_V

    R = int(input())
    for i in range(R):#swap
        s,t = list(map(int,input().split()))
        w = izua[t]
        izua[t] = izua[s]
        izua[s] = w

    res = 0
    for i in range(N,0,-1):
        res += (bit.sum(izua[i])*dp[N-i]) % MOD_V 
        bit.update(izua[i],1)

    print (res%MOD_V)