Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

from collections import deque
n,m,k=map(int,input().split())

F=[set() for i in range(n)]
B=[set() for i in range(n)]
for i in range(m):
	a,b=map(int,input().split())
	a,b=a-1,b-1
	F[a].add(b)
	F[b].add(a)
for i in range(k):
	c,d=map(int,input().split())
	c,d=c-1,d-1
	B[c].add(d)
	B[d].add(c)
	
T=[set() for i in range(n)]
D=[0]*n
for i in range(n):
	if D[i]:
	    continue
	que=deque([])
	que.append(i)
	T[i].add(i)
	while que:
	    p=que.popleft()
	    for np in F[p]:
	        if D[np]!=1:
	            que.append(np)
	            T[i].add(np)
	            D[np]=1

S=[[] for i in range(n)]
for i in range(n):
    if T[i]:
        for t in T[i]:
            S[t]=list(T[i])[:]
            S[t].remove(t)
		
R=[0]*n
for i in range(n):
	R[i]=len(S[i])-len(F[i])-len(set(S[i])&set(B[i]))
print(*R)

### FIXED CODE ###

from collections import deque
n,m,k=map(int,input().split())

F=[set() for i in range(n)]
B=[set() for i in range(n)]
for i in range(m):
	a,b=map(int,input().split())
	a,b=a-1,b-1
	F[a].add(b)
	F[b].add(a)
for i in range(k):
	c,d=map(int,input().split())
	c,d=c-1,d-1
	B[c].add(d)
	B[d].add(c)
	
T=[set() for i in range(n)]
D=[0]*n
R=[0]*n

for i in range(n):
    if D[i]:
        continue
    que=deque([])
    que.append(i)
    S=set()
    S.add(i)
    while que:
        p=que.popleft()
        for np in F[p]:
            if D[np]!=1:
                que.append(np)
                S.add(np)
                D[np]=1
    for s in S:
        R[s]=len(S)-len(F[s])-len(S&B[s])-1

print(*R)
### BUGGY CODE ###

import numpy as np
import collections

alpha2num = lambda c:ord(c) - ord('a')

N = int(input())
D = np.zeros([26,N])
SUM = 0

for n in range(N):
  s = input()
  c = collections.Counter(s)
  for _c in c.keys():
    i = alpha2num(_c)
    D[i, n] = c[_c]
    
  d = D[:,n]
  d = d.reshape(len(d),1)
  diff = D - d
  count = sum(np.square(diff))
  k = np.count_nonzero(count == 0)
  SUM = SUM + k
  
print('%d' % (SUM-N))
  
  

### FIXED CODE ###

N = int(input())
D = {}
SUM = 0

for n in range(N):
  s = input()
  l = sorted(s)
  l = ''.join(l)
  
  if l in D:
    SUM = SUM + D[l]
    D[l] = D[l] + 1
  else:
    D[l] = 1
  
print(SUM)
### BUGGY CODE ###

import sys
input=sys.stdin.readline
n,m=map(int,input().split())
a=[int(input()) for i in range(m)]
dp=[0]*(n+1)
dp[0]=1
for i in range(1,n+1):
    dp[i]=(dp[i-1]+dp[i-2])%(10**9+7)
    if i in a:dp[i]=0
print(dp[n])

### FIXED CODE ###

n,m=map(int,input().split())
A=set(int(input()) for i in range(m))
dp=[0]*(n+1)
dp[0]=1
for i in range(1,n+1):
    dp[i]=(dp[i-1]+dp[i-2])%(10**9+7)
    if i in A:dp[i]=0
print(dp[n])
### BUGGY CODE ###

n,k=map(int,input().split())
h=[int(i) for i in input().split()]

dp=[float('inf')]*n
dp[0]=0

for i in range(1,n):
    for j in range(k):
        if i-1-j<0:
            break
        dp[i]=min(dp[i],dp[i-1-j]+abs(h[i]-h[i-1-j]))
print(dp[-1])

### FIXED CODE ###

n,k=map(int,input().split())
h=[int(i) for i in input().split()]

dp=[float('inf')]*n
dp[0]=0

for i in range(1,n):
    for j in range(k):
        if i-1-j<0:
            break
        dp[i]=min(dp[i],dp[i-1-j]+abs(h[i]-h[i-1-j]))
print(dp[-1])
### BUGGY CODE ###

s = input()
K = int(input())
n = len(s)
A =[]
import bisect
for i in range(n):
    for j in range(1,K+1):
        sub = s[i:i+j]  
        if sub not in A:
            x = bisect.bisect_left(A,sub)
            A.insert(x,sub)

print(A[K-1])

### FIXED CODE ###

s = input()
K = int(input())
n = len(s)
A =[]
import bisect
for i in range(n):
    for j in range(1,K+1):
        sub = s[i:i+j]  
        if sub not in A:
            x = bisect.bisect_left(A,sub)
            A.insert(x,sub)
            if len(A) > K:
                A.pop(K)

print(A[K-1])
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def inp_str():
    '''
    一行の文字をlistで取得
    '''
    return list(input())

s = inp_str()
t = inp_str()
n = len(s)-1
m = len(t)-1
value = [[0]*(m+1) for i in range(n+1)]
ans = [[""]*(m+1) for i in range(n+1)]


for i in range(n):
    for j in range(m):
        if s[i] == t[j]:
            value[i + 1][j + 1] = value[i][j] + 1
            ans[i + 1][j + 1] = "".join([ans[i][j], s[i]])
        elif value[i][j + 1] > value[i + 1][j]: #UP
            ans[i + 1][j + 1] = ans[i][j + 1]
            value[i + 1][j + 1] = value[i][j + 1]
        else:  # LEFT
            ans[i + 1][j + 1] = ans[i + 1][j]
            value[i + 1][j + 1] = value[i + 1][j]

print(ans[n][m])


### FIXED CODE ###

import sys
input = sys.stdin.readline

s = list(input())
t = list(input())
n = len(s)-1
m = len(t)-1
value = [[0]*(m+1) for i in range(n+1)]


for i in range(n):
    for j in range(m):
        if s[i] == t[j]:
            value[i + 1][j + 1] = value[i][j] + 1
        elif value[i][j + 1] > value[i + 1][j]: #UP
            value[i + 1][j + 1] = value[i][j + 1]
        else:  # LEFT
            value[i + 1][j + 1] = value[i + 1][j]
i = n-1
j = m-1
ans=""
while i >= 0 and j >= 0:
    if s[i] == t[j]:
        ans = s[i] + ans
        i -= 1
        j -= 1
    elif value[i][j + 1] > value[i + 1][j]:
        i -= 1
    else:
        j -= 1
print(ans)
### BUGGY CODE ###

from collections import deque

h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]
move = [(1,0), (0,1), (-1,0), (0,-1)]

queue = deque([(row, col, 0) for row in range(h) for col in range(w) if a[row][col] == "#"])
visited = [[-1]*w for _ in range(h)]

max_dist = 0
while queue:
    row, col, dist = queue.popleft()
    if visited[row][col] == -1:
        visited[row][col] = 0
    if max_dist < dist:
        max_dist = dist
    for drow, dcol in move:
        if a[row+drow:row+drow+1] and a[row+drow][col+dcol:col+dcol+1] and visited[row+drow][col+dcol] == -1 and a[row+drow][col+dcol] == ".":
            visited[row+drow][col+dcol] == dist + 1
            queue.append((row+drow, col+dcol, dist+1))


print(max_dist)


### FIXED CODE ###

from collections import deque

h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]
move = [(1,0), (0,1), (-1,0), (0,-1)]

queue = deque()
visited = [[-1] * w for _ in range(h)]
for row in range(h):
    for col in range(w):
        if a[row][col] == "#":
            visited[row][col] = 0
            queue.append((row, col, 0))
dist = 0
while queue:
    row, col, dist = queue.popleft()
    for drow, dcol in move:
        if a[row+drow:row+drow+1] and a[row+drow][col+dcol:col+dcol+1] and visited[row+drow][col+dcol] == -1 and a[row+drow][col+dcol] == ".":
            visited[row+drow][col+dcol] = dist + 1
            queue.append((row+drow, col+dcol, dist+1))


print(dist)
### BUGGY CODE ###

n, k = list(map(int, input().split()))
p = list(map(int, input().split()))

c = [None]*(n-k+1)
t = [0]*(n-k+1)
ttl = 0
for i in range(0, n-k+1):
    c[i] = p[i:k+i]
    cs = sum(c[i])
    if ttl < cs:
        ttl = cs
        t[i] = i
ans = 0
for j in c[max(t)]:
    ans += (j*(j+1)/2)/j

print(ans)

### FIXED CODE ###

n, k = list(map(int, input().split()))
p = list(map(int, input().split()))
r = [0]*(n + 1)
for i in range(1,n + 1):
    r[i] += r[i - 1] + (p[i - 1] + 1) / 2
ans = 0
for j in range(n - k + 1):
    ans = max(ans, r[j+k] - r[j])
print(ans)
### BUGGY CODE ###

n = int(input())
a =  int(input())
b =  int(input())
c =  int(input())
d =  int(input())
e =  int(input())
lst = [n] + [0] * 5
#print ('0', lst)
i = 0
tmp0 = 0

lst[0] != 0
tmp0 = min(lst[0], a)
lst[0] -= tmp0
lst[1] += tmp0
#print ('1', lst)

lst[1] != 0
tmp0 = min(lst[1], b)
lst[1] -= tmp0
lst[2] += tmp0
lst[0] != 0
tmp0 = min(lst[0], a)
lst[0] -= tmp0
lst[1] += tmp0
#print ('2', lst)

lst[2] != 0
tmp0 = min(lst[2], c)
lst[2] -= tmp0
lst[3] += tmp0
lst[1] != 0
tmp0 = min(lst[1], b)
lst[1] -= tmp0
lst[2] += tmp0
lst[0] != 0
tmp0 = min(lst[0], a)
lst[0] -= tmp0
lst[1] += tmp0
#print ('3', lst)

lst[3] != 0
tmp0 = min(lst[3], d)
lst[3] -= tmp0
lst[4] += tmp0
lst[2] != 0
tmp0 = min(lst[2], c)
lst[2] -= tmp0
lst[3] += tmp0
lst[1] != 0
tmp0 = min(lst[1], b)
lst[1] -= tmp0
lst[2] += tmp0
lst[0] != 0
tmp0 = min(lst[0], a)
lst[0] -= tmp0
lst[1] += tmp0
#print ('4', lst)

lst[4] != 0
tmp0 = min(lst[4], e)
lst[4] -= tmp0
lst[5] += tmp0
lst[3] != 0
tmp0 = min(lst[3], d)
lst[3] -= tmp0
lst[4] += tmp0
lst[2] != 0
tmp0 = min(lst[2], c)
lst[2] -= tmp0
lst[3] += tmp0
lst[1] != 0
tmp0 = min(lst[1], b)
lst[1] -= tmp0
lst[2] += tmp0
lst[0] != 0
tmp0 = min(lst[0], a)
lst[0] -= tmp0
lst[1] += tmp0
#print ('5', lst)

while i < (n + 4):
    if lst == [0, 0, 0, 0, 0, n]:
        print (i + 5)
        break
    else:
        i +=1
    if lst[4] != 0:
        tmp0 = min(lst[4], e)
        lst[4] -= tmp0
        lst[5] += tmp0
    if lst[3] != 0:
        tmp0 = min(lst[3], d)
        lst[3] -= tmp0
        lst[4] += tmp0
    if lst[2] != 0:
        tmp0 = min(lst[2], c)
        lst[2] -= tmp0
        lst[3] += tmp0
    if lst[1] != 0:
        tmp0 = min(lst[1], b)
        lst[1] -= tmp0
        lst[2] += tmp0
    if lst[0] != 0:
        tmp0 = min(lst[0], a)
        lst[0] -= tmp0
        lst[1] += tmp0
#    print (lst)

### FIXED CODE ###

n = int(input())
a =  int(input())
b =  int(input())
c =  int(input())
d =  int(input())
e =  int(input())

m = min(a, b, c, d, e)

print ((n + m -1)//m + 4)
### BUGGY CODE ###

k=input()
r=int(k)
s=7
j=0
l=len(k)-1
if(r%2==0):
  print("-1")
elif(k[l]=='1' or k[l]=='3' or k[l]=='7' or k[l]=='9'):
    while(1):
        j=j+1
        if(s%r==0):
            break
        s=s*10+7
    print(j)
else:
    print("-1")

### FIXED CODE ###

k=int(input())
s=7
x=10000000
for i in range(x):
    if(s%k==0):
        print(i+1)
        break
    s=(s%k)*10+7
if(s%k!=0):
    print("-1")
### BUGGY CODE ###

import sys
import bisect
import itertools
import collections
import fractions
import heapq
import math
from operator import mul
from functools import reduce
from functools import lru_cache


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    x, y = map(int, readline().split())
    ans = 0
    ilist = [1]
    tmp = 1
    for i in range(1, max(x,y)+1):
        tmp *= i
        ilist.append(tmp)
    for b in range(x//2+1):
        a = x - 2 * b
        if 2*a + b == y:
            ans += ilist[a+b] // ilist[b] //ilist[a]
    print(ans)


if __name__ == '__main__':
    solve()

### FIXED CODE ###

import sys
import bisect
import itertools
import collections
import fractions
import heapq
import math
from operator import mul
from functools import reduce
from functools import lru_cache


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    x, y = map(int, readline().split())
    ans = 0
    tmp = 1

    def modinv(a, mod=10 ** 9 + 7):
        return pow(a, mod - 2, mod)

    def com(n, r, mod):
        r = min(r, n - r)
        if r == 0:
            return 1
        res = ilist[n] * iinvlist[n - r] * iinvlist[r] % mod
        return res

    ilist = [0]
    iinvlist = [1]
    tmp = 1


    for i in range(1, x + y + 1):
        tmp *= i
        tmp %= mod
        ilist.append(tmp)
        iinvlist.append(modinv(tmp, mod))


    for b in range(x//2+1):
        a = x - 2 * b
        if 2*a + b == y:
            ans += ilist[a+b] * iinvlist[a] * iinvlist[b] % mod
    print(ans)


if __name__ == '__main__':
    solve()
### BUGGY CODE ###

n=int(input())
s = [ str(input()) for _ in range(n)]
s = [sorted(x) for x in s]
pairs =[]
for i in range(n):
    for j in range(i+1, n):
        if s[i] == s[j]:
            pairs.append(tuple([i,j]))
print(len(pairs))

### FIXED CODE ###

n=int(input())
s = [ str(input()) for _ in range(n)]
s = sorted([sorted(x) for x in s])
pairs = 0
from operator import mul
from functools import reduce

def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom

i=0
while i < n-1:
    sames = 0
    for j in range(i+1, n):
        if s[i] == s[j]:
            sames += 1
            continue
        else:
            break
    i += sames + 1
    if sames != 0:
        pairs += combinations_count(sames + 1, 2)


print(int(pairs))
### BUGGY CODE ###

N = int(input())
abc = [chr(i) for i in range(97, 97+26)]
ss = []
ct = []
ans = 0

for i in range(N):
    s = input()
    cnt = []
    for j in abc:
        num = s.count(j)
        cnt.append(num)
    if not cnt in ss:
        ss.append(cnt)
        ct.append(1)
    else:
        ct[ss.index(cnt)] += 1

for i in range(len(ct)):
    if ct[i] > 1:
        ans += int((ct[i] * (ct[i] - 1))/2)


print(ans)


### FIXED CODE ###

N = int(input())
ss = {}
ht = []
ans = 0

for i in range(N):
    s = ''.join(sorted(input()))
    if not s in ss.keys():
        ss[s] = 1
    else:
        ans += ss[s]
        ss[s] += 1

print(ans)
### BUGGY CODE ###

from collections import defaultdict
def resolve():
    n, m = map(int, input().split())
    h = list(map(int, input().split()))

    d = defaultdict(list)
    for _ in range(m):
        ai, bi = map(lambda x: int(x) - 1, input().split())
        d[ai].append(bi)
        d[bi].append(ai)

    bad = []
    ans = 0
    for i in range(n):
        if i in bad:
            continue
        flg = True
        for nei_peak in d[i]:
            if h[i] <= h[nei_peak]:
                flg = False
                break

        if flg:
            ans += 1
            for nei_peak in d[i]:
                bad.append(nei_peak)


    print(ans)
    
resolve()

### FIXED CODE ###

from collections import defaultdict
def resolve():
    n, m = map(int, input().split())
    h = list(map(int, input().split()))

    d = defaultdict(list)
    for _ in range(m):
        ai, bi = map(lambda x: int(x) - 1, input().split())
        d[ai].append(bi)
        d[bi].append(ai)

    bad = []
    ans = 0
    for i in range(n):
        if -1 in d[i]:
            continue
        flg = True
        for nei_peak in d[i]:
            if h[i] <= h[nei_peak]:
                flg = False
                break

        if flg:
            ans += 1
            for nei_peak in d[i]:
                d[nei_peak] = [-1]

    print(ans)
resolve()
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()
list = []
for i in range(Q):
    l,r = map(int, input().split())
    list.append([l,r])

#print(list)

target_s = 'AC'
for i in range(Q):
    sub_S = S[list[i][0]-1:list[i][1]]
    #print(i,sub_S)
    count = 0
    for j in range(len(sub_S)+1-len(target_s)):
        sub_sub_S = sub_S[j:j+len(target_s)]
        #print(sub_sub_S)
        if sub_sub_S == target_s:
            count += 1
    print(count)

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
list = [[0 for i in range(2)] for j in range(Q)]

b = [0] * (N+1)
for i in range(N):
    if S[i:i+2] == 'AC':
        b[i+1] = b[i] + 1
    else:
        b[i+1] = b[i]
for i in range(Q):
    l,r = map(int, input().split())
    print(b[r-1]-b[l-1])
### BUGGY CODE ###

from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix

N, M, S, T, *UVAB = map(int, open(0).read().split())
A, B, R, C = [], [], [], []
for u, v, a, b in zip(*[iter(UVAB)] * 4):
    A.append(a)
    B.append(b)
    R.append(u)
    C.append(v)

A = dijkstra(csr_matrix((A, (R, C)), (N + 1, N + 1)), False, S)
B = dijkstra(csr_matrix((B, (R, C)), (N + 1, N + 1)), False, T)

C = (A + B).astype(int)

init = 10 ** 15
ans = []
cur = float("inf")
for c in reversed(C[1:]):
    cur = min(cur, c)
    ans.append(init - cur)

for a in reversed(ans):
    print(a)

### FIXED CODE ###

from heapq import heappush, heappop

INF = float("inf")
def dijkstra(E, r):
    D = [INF] * len(E)
    D[r] = 0

    Q = [(0, r)]
    while Q:
        dist, cur = heappop(Q)
        for nxt, cost in E[cur]:
            cand = dist + cost
            if D[nxt] > cand:
                D[nxt] = cand
                heappush(Q, (cand, nxt))

    return D


N, M, S, T, *UVAB = map(int, open(0).read().split())
A = [[] for _ in range(N + 1)]
B = [[] for _ in range(N + 1)]
for u, v, a, b in zip(*[iter(UVAB)] * 4):
    A[u].append((v, a))
    A[v].append((u, a))
    B[u].append((v, b))
    B[v].append((u, b))

A = dijkstra(A, S)
B = dijkstra(B, T)

init = 10 ** 15

ans = []
cur = INF
for a, b in zip(reversed(A[1:]), reversed(B[1:])):
    cur = min(cur, a + b)
    ans.append(init - cur)

for a in reversed(ans):
    print(a)
### BUGGY CODE ###

n,m=list(map(int,input().split(" ")))
al=[0 for i in range(n)]
bl=[0 for i in range(n)]
for i in range(n):
    al[i],bl[i]=list(map(int,input().split(" ")))
    have=0
yen=0
while have<m:
    k=al.index(min(al))
    pri=al.pop(k)
    num=bl.pop(k)
    have+=num
    yen+=pri*num
if have>m:
    yen-=(have-m)*pri
print(yen)

### FIXED CODE ###

n,m=list(map(int,input().split(" ")))
l=[]
l=[list(map(int,input().split(" "))) for i in range(n)]
have=0
yen=0
i=0
l.sort(key=lambda x: x[0])
while have<m:
    pri=l[i][0]
    num=l[i][1]
    i+=1
    have+=num
    yen+=pri*num
if have>m:
    yen-=(have-m)*pri
print(yen)
### BUGGY CODE ###

from collections import deque

def isCLKWISE(ph):
    a = [ph[-1][0]-ph[-3][0],ph[-1][1]-ph[-3][1]]
    b = [ph[-2][0]-ph[-3][0],ph[-2][1]-ph[-3][1]]
    crs = a[0]*b[1] - a[1]*b[0]
    if crs < 0 :
        return False
    else :
        return True
    
def ConvexHullScan(P):
    P = sorted(P)
    phU = [P[0],P[1]]
    for p in P[2:]:
        phU.append(p)
        while(True):
            if isCLKWISE(phU) :
                break
            else :
                phU.remove(phU[-2])
                if len(phU) == 2 :
                    break
    phL = [P[-1],P[-2]]
    for p in P[-3::-1]:
        phL.append(p)
        while(True):
            if isCLKWISE(phL) :
                break
            else :
                del phL[-2]
                if len(phL) == 2 :
                    break
    ph = phU + phL[1:-1]
    return ph

n = int(input())
P = deque([])
for i in range(n):
    P.append([int(x) for x in input().split()])
    
Q = ConvexHullScan(P)
Q.reverse()
print(len(Q))
for q in Q:
    idx = min([[x[1][1],x[1][0],x[0]] for x in enumerate(Q)])[2]
    R = Q[idx:] + Q[:idx]
for r in R:
    print(r[0],r[1])

### FIXED CODE ###

def isCLKWISE(ph) : return not ((ph[-1][0] - ph[-3][0])*(- ph[-3][1] + ph[-2][1]) - (ph[-2][0] - ph[-3][0])*(- ph[-3][1] + ph[-1][1] ) < 0)
      
def ConvexHullScan(P):
    P = sorted(P)
    phU = [P[0],P[1]]
    for p in P[2:]:
        phU.append(p)
        while(True):
            try :
                if isCLKWISE(phU) : break
                else : del phU[-2]
            except IndexError : break
    phL = [P[-1],P[-2]]
    for p in P[-3::-1]:
        phL.append(p)
        while(True):
            try :
                if isCLKWISE(phL) : break
                else : del phL[-2]
            except IndexError : break
    ph = phU + phL[1:-1]
    return ph
  
P = [[int(x) for x in input().split()] for _ in range(int(input()))]
P = ConvexHullScan(P)
P.reverse()
print(len(P))
idx = min([[x[1][1],x[1][0],x[0]] for x in enumerate(P)])[2]
for p in P[idx:] + P[:idx] : print(p[0],p[1])
### BUGGY CODE ###

#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n=int(input())
A=list(map(int,input().split()))
def gcd(a, b):
    while(b != 0):
        a, b = b, a % b
    return a
    
def lcm(m,n):
    return (m*n)//gcd(m,n)
for ai in A:
    pro=lcm(pro,ai)
for ai in A:
    count+=pro//ai
    count%=mod
print(count)


### FIXED CODE ###

#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n=int(input())
A=list(map(int,input().split()))


def gcd(a, b):
    while(b != 0):
        a, b = b, a % b
    return a
    
def lcm(m,n):
    return (m*n)//gcd(m,n)

P = 10**9 + 7
N = 1000010
inv_t = [0]+[1]
for i in range(2,N):
  inv_t += [inv_t[P % i] * (P - int(P / i)) % P]

for ai in A:
    pro=lcm(pro,ai)
for ai in A:
    ans+=inv_t[ai]
    ans%=mod
print((pro*ans)%mod)

# pro2=1
# for ai in A:
#     pro2=(pro2*ai)%mod
#     pro=gcd(pro,ai)
# for ai in A:
#     count+=pro//ai
#     count%=mod
# print(count)
### BUGGY CODE ###

n = int(input())
ans = 1
for i in range(1,n+1):
  ans *= i
print(ans % (10 **9 + 7))

### FIXED CODE ###

n = int(input())
ans = 1
for i in range(1,n+1):
  ans *= i
  ans %= (10**9 + 7)
print(ans)
### BUGGY CODE ###

import sys
import numpy as np

sys.setrecursionlimit(10 ** 9)
mod = 10**9+7

H, W = map(int,input().split())
#A = [list(map(int,input().split())) for _ in range(H)]
A = np.array([list(input()) for _ in range(H)], 'U1')
eq = A == '.'

dp = np.zeros(W+1, dtype=int)
dp[1] = 1

for i in range(1,H+1):
    prev = dp.copy()
    for j in range(1,W+1):
        if eq[i-1][j-1]:
            dp[j] = prev[j] + dp[j-1]
        else:
            dp[j] = 0
        dp %= mod

print(dp[-1])

### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sun Jan  6 21:36:22 2019

@author: Yamazaki Kenichi
"""

H,W = map(int,input().split())
a = [input() for i in range(H)]

r =[[0]*W for i in range(H)]
r[0][0]=1


for i in range(1,W):
    if a[0][i]== '.':
        r[0][i] = r[0][i-1]

for j in range(1,H):
    if a[j][0] =='.':
        r[j][0] = r[j-1][0]
            
for j in range(1,H):
    for i in range(1,W):
        if a[j][i] == '.':
            r[j][i] = r[j-1][i]+r[j][i-1]

print(r[H-1][W-1]%1000000007)
### BUGGY CODE ###

from bisect import bisect_left


def count_inversion(A):
    cnt = 0
    for i in reversed(range(len(A) - 1)):
        j = bisect_left(A, A[i], i + 1, len(A))
        cnt += j - i - 1
        tmp = A[i]
        del A[i]
        A.insert(j - 1, tmp)
    return cnt


def main():
    n = int(input())
    A = [int(x) for x in input().split()]
    print(count_inversion(A))


main()



### FIXED CODE ###

#! /usr/local/bin/python3
# coding: utf-8

from math import inf

inv = 0


def merge(A, left, mid, right):
    global inv

    L = A[left:mid]
    L.append(inf)
    R = A[mid:right]
    R.append(inf)
    i = j = 0
    for k in range(left, right):
        if L[i] < R[j]:
            A[k] = L[i]
            i += 1
        else:
            inv += len(L) - i - 1
            A[k] = R[j]
            j += 1


def merge_sort(A, left, right):
    if left + 1 < right:
        mid = (left + right) // 2
        merge_sort(A, left, mid)
        merge_sort(A, mid, right)
        merge(A, left, mid, right)


def main():
    n = int(input())
    A = [int(x) for x in input().split()]
    merge_sort(A, 0, n)
    print(inv)


main()
### BUGGY CODE ###

s = input()
K = int(input())

list_rank = []
for i in range(len(s)):
    if i < len(s) - K + 1:
        for j in range(K+1):
            if s[i:i+j+1] not in list_rank:
                list_rank.append(s[i:i+j+1])
    else:
        for j in range(len(s)-i):
            if s[i:i+j+1] not in list_rank:
                list_rank.append(s[i:i+j+1])

list_rank.sort()
print(list_rank[K-1])


### FIXED CODE ###

s = input()
K = int(input())

ct = 0
alp = 'abcdefghijklmnopqrstuvwxyz'
for i in alp:
    ct += s.count(i)
    if ct >= K:
        break

key = i

list_rank = []
for i in range(len(s)):
    if s[i] > key:
        continue
    if i < len(s) - K + 1:
        for j in range(K):
            if s[i:i+j+1] not in list_rank:
                list_rank.append(s[i:i+j+1])
    else:
        for j in range(len(s)-i):
            if s[i:i+j+1] not in list_rank:
                list_rank.append(s[i:i+j+1])

list_rank.sort()
print(list_rank[K-1])
### BUGGY CODE ###

num = int(input())
line = input().split()
line2 = [0]* num

#studentの数字=出席順
for student in line:
  line2[int(student)-1] += line.index(student) + 1


print(" ".join(map(str,line2)))

### FIXED CODE ###

num=int(input())
line=list(map(int,input().split()))
line2=[0]*num
for i in range(num):
  line2[line[i]-1]=i+1
print(" ".join(map(str,line2)))