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

N, M ,K= map(int, input().split())
a=[0]*M
b=[0]*M
c=[0]*K
d=[0]*K

for i in range(M):
    a[i], b[i] = map(int, input().split())
for i in range(K):
    c[i], d[i] = map(int, input().split())
l=[-1]*(N+1)
la=N

for i in range(M):
    if l[a[i]]<0 and l[b[i]]<0:
        l[a[i]]=la
        l[b[i]]=la
        la-=1
    elif l[a[i]]>l[b[i]]:
        if l[b[i]]>0:
            l=[x if x is not l[b[i]] else l[a[i]] for x in l ]
        else:
            l[b[i]]=l[a[i]]

    else:
        if l[a[i]] > 0:
            l = [x if x is not l[a[i]] else l[b[i]] for x in l]
        else:
            l[a[i]]=l[b[i]]

t=[]

for i in range(1,N+1):

    if l[i]>0:
        p=l.count(l[i])-1
        indexes = [j for j, x in enumerate(a) if x == i]
        for j in range(len(indexes)):
            if l[b[indexes[j]]]==l[i]:
                p-=1
        indexes = [j for j, x in enumerate(b) if x == i]
        for j in range(len(indexes)):
            if l[a[indexes[j]]] == l[i]:
                p -= 1
        indexes = [j for j, x in enumerate(d) if x == i]
        for j in range(len(indexes)):
            if l[c[indexes[j]]] == l[i]:
                p -= 1
        indexes = [j for j, x in enumerate(c) if x == i]
        for j in range(len(indexes)):
            if l[d[indexes[j]]] == l[i]:
                p -= 1


    else:
        p=0
    t.append(p)

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

### FIXED CODE ###

N, M ,K= map(int, input().split())
a=[0]*M
b=[0]*M
c=[0]*K
d=[0]*K

for i in range(M):
    a[i], b[i] = map(int, input().split())
for i in range(K):
    c[i], d[i] = map(int, input().split())

l=list(range(N+1))
r=[0]*(N+1)
size=[1]*(N+1)
la=N
di=[[]for _ in range(N+1)]
def find(x):
    if l[x]==x:
        return x
    else:
        return find(l[x])

def union(x,y):
    X=find(x)
    Y=find(y)
    if r[X]>r[Y]:
        l[Y]=l[X]
        size[X]+=size[Y]
    else:
        l[X]=l[Y]

        if r[X]==r[Y]:
            r[Y]+=1
        if X!=Y:
            size[Y] += size[X]
for i in range(M):
    union(a[i],b[i])
    di[a[i]].append(b[i])
    di[b[i]].append(a[i])
for i in range(K):
    if (find(c[i])==find(d[i])):
        di[c[i]].append(d[i])
        di[d[i]].append(c[i])

t=[]
for i in range(N+1):
    p=size[find(i)]-1-len(di[i])

    t.append(p)


print(" ".join(map(str, t[1:])))
### BUGGY CODE ###

n, m = map(int, input().split())
al = map(int, input().split())
ad = {}
for a in al:
    if a not in ad:
        ad[a] = 1
    else:
        ad[a] += 1


keys = list(ad.keys())
keys.sort()
for i in range(m):
    b, c = map(int, input().split())
    
    if c == 1:
        break
    
    changed = False
    for a in keys:

        if a >= c:
            break
        
        k = 0
        if b > ad[a]:
            k = ad[a]
            ad[a] = 0
            b -= k
        else:
            ad[a] -= b
            k = b
            b = 0
        
        if c not in ad:
            ad[c] = k
            changed = True
        else:
            ad[c] += k
        

    if changed:
        keys = list(ad.keys())
        keys.sort()


sum = 0
for a in ad.keys():
    sum += a * ad[a]

print(sum)

### FIXED CODE ###

import heapq


n, m = map(int, input().split())
al = map(int, input().split())
h = []
ad = {}
for a in al:
    if a not in ad:
        ad[a] = 1
    else:
        ad[a] += 1
    

for i in range(m):
    b, c = map(int, input().split())
    
    if c not in ad:
        ad[c] = b
    else:
        ad[c] += b


keys = list( ad.keys() )
keys.sort(reverse=True)



for k in keys:
    for i in range(ad[k]):
        heapq.heappush(h, k)

        if len(h) >= n:
            break


ans = sum( heapq.nlargest(n, h) )
print(ans)
### BUGGY CODE ###

n=int(input())

ans=0

for i in range(1, n+1):
    begin=i
    end=(n//i)*i
    cnt=(n//i)
    ans+=(1/2)*cnt*(begin+end)

print(int(ans))

### FIXED CODE ###

n=int(input())

ans=0

for i in range(1, n+1):
    begin=i
    end=(n//i)*i
    cnt=(n//i)
    ans+=(1/2)*cnt*(begin+end)

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

N = int(input())
A = list(map(int, input().split()))
B = []
for i in range(N):
  B.append([A[i], i])
B.sort()
ANS = ""
for i in range(N):
  ANS += str(B[i][1]+1)
  if i != N-1:
    ANS += " "
print(ANS)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
B = [0 for i in range(N)]
for i in range(N):
  B[A[i]-1] = i
for b in B:
  print(b+1)
### BUGGY CODE ###

import sys
N=int(input())
A=list(map(int,input().split()))
tmp=[]
for i in A:
    if not i in tmp:
        tmp.append(i)
    else:
        print('NO')
        sys.exit()
print('YES')

### FIXED CODE ###

import sys
N=int(input())
A=list(map(int,input().split()))
A.sort()
for i in range(1,N):
    if A[i-1]==A[i]:
        print('NO')
        sys.exit()
print('YES')
### BUGGY CODE ###

N=int(input())
S=list(input())
flag=1
count=0
for i in range(1000):
  numS=''
  flag=1
  if i<10:
    numS='00'+str(i)
  elif i<100:
    numS='0'+str(i)
  else:
    numS=str(i)
  for j in range(N):
    if numS[0]==S[j]:
      for k in range(j+1,N):
        if numS[1]==S[k]:
          if numS[2] in S[k+1:]:
            count+=1
            flag=0
            break
          else:
            flag=0
            break
        elif k==N and flag==1:
          flag=0
    if flag==0:
      break

print(count)

### FIXED CODE ###

N = int(input())
S = input()
s1 = set()
s2 = set()
s3 = set()

for i in S:
  for j in s2:
    s3.add(j+i)
  for k in s1:
    s2.add(k+i)
  s1.add(i)
print(len(s3))
### BUGGY CODE ###

from collections import deque
H, W = map(int, input().split())
sH, sW = map(int, input().split())
sH, sW = sH - 1, sW - 1
gH, gW = map(int, input().split())
gH, gW = gH - 1, gW - 1
stage = []
scores = []
for _ in range(H):
    stage.append(list(input()))
    scores.append([float('inf')] * W)
scores[sH][sW] = 0
move_q = deque()
move_q.append([sW, sH])
dx_list = [0, 1, 0, -1]
dy_list = [1, 0, -1, 0]
while move_q:
    while move_q:
        # 移動AでBFS
        x, y = move_q.pop()
        for dx, dy in zip(dx_list, dy_list):
            nx, ny = x + dx, y + dy
            if nx < 0 or W <= nx or ny < 0 or H <= ny or stage[ny][nx] == '#':
                continue
            # if scores[ny][nx] == float('inf'):
            if scores[ny][nx] > scores[y][x]:
                scores[ny][nx] = scores[y][x]
                move_q.appendleft([nx, ny])

        # 移動bで動けるマスをmodeA_qに格納
        for dx in range(-2, 3):
            for dy in range(-2, 3):
                nx, ny = x + dx, y + dy
                if nx < 0 or W <= nx or ny < 0 or H <= ny or stage[ny][nx] == '#':
                    continue
                # if scores[ny][nx] == float('inf'):
                if scores[ny][nx] > scores[y][x]:
                    scores[ny][nx] = scores[y][x] + 1
                    move_q.append([nx, ny])


# print(*scores,sep='\n')
if scores[gH][gW] == float('inf'):
    print(-1)
else:
    print(scores[gH][gW])


### FIXED CODE ###

from collections import deque
H, W = map(int, input().split())
sH, sW = map(int, input().split())
sH, sW = sH - 1, sW - 1
gH, gW = map(int, input().split())
gH, gW = gH - 1, gW - 1
stage = []
scores = []
for _ in range(H):
    stage.append(list(input()))
    scores.append([float('inf')] * W)
scores[sH][sW] = 0
moveA_q = deque()
moveB_q = deque()
moveA_q.append([sW, sH])
moveB_q.append([sW, sH])
dx_list = [0, 1, 0, -1]
dy_list = [1, 0, -1, 0]
while moveA_q:
    if scores[gH][gW] != float('inf'):
        break
    # 移動AでBFS
    x, y = moveA_q.pop()
    moveB_q.append([x, y])
    for dx, dy in zip(dx_list, dy_list):
        nx, ny = x + dx, y + dy
        if nx < 0 or W <= nx or ny < 0 or H <= ny or stage[ny][nx] == '#':
            continue
        if scores[ny][nx] == float('inf'):
        # if scores[ny][nx] > scores[y][x]:
            scores[ny][nx] = scores[y][x]
            moveA_q.append([nx, ny])

    if not moveA_q:
        # 移動bで動けるマスをmodeA_qに格納
        while moveB_q:
            x, y = moveB_q.pop()
            for dx in range(-2, 3):
                for dy in range(-2, 3):
                    nx, ny = x + dx, y + dy
                    if nx < 0 or W <= nx or ny < 0 or H <= ny or stage[ny][nx] == '#':
                        continue
                    if scores[ny][nx] == float('inf'):
                    # if scores[ny][nx] > scores[y][x]:
                        moveA_q.append([nx, ny])
                        scores[ny][nx] = scores[y][x] + 1

# print(*scores,sep='\n')
if scores[gH][gW] == float('inf'):
    print(-1)
else:
    print(scores[gH][gW])
### BUGGY CODE ###

# encoding: "utf-8"

class Stdin:
    @staticmethod
    def read_line(converter=str):
        return [converter(x) for x in input().split()]
    
    @staticmethod
    def read_lines(n, converter=str):
        result = list()
        for _ in range(n):
            result.append(Stdin.read_line(converter))
        return result
    
    @staticmethod
    def convert(data, converter):
        assert(len(data) == len(converter))
        return tuple(map(lambda x, f: f(x), data, converter))

    @staticmethod
    def convert_lines(datas, n, converter):
        return [converter(data, n, converter) for data in datas]


def first_count_and_pop(xs):
    cnt = 0
    fst = xs[0]
    cnt = xs.count(fst)
    # for x in xs:
    #     if x != fst:
    #         break
    #     cnt += 1
    return (cnt, xs[cnt:])    
    

def main():
    _ = input()
    xs = Stdin.read_line(converter=int)
    xs.sort()
    ys = dict()
    while xs:
        key = xs[0]
        cnt, xs = first_count_and_pop(xs)
        ys[key] = cnt
    if len(xs) == len(ys.keys()):
        print(3)
        return
    zs = sorted(list(ys.items()), key=(lambda x: x[1]), reverse=True)
    m = 0
    for (i, x) in zs:
        temp = ys.get(i-1, 0) + x + ys.get(i+1, 0)
        if m < temp:
            m = temp
        else:
            break
    print(m)

if __name__ == "__main__":
    main()

### FIXED CODE ###

input()
a_list = [int(s) for s in input().split()]

count = [0]*100002

for a in a_list:
    count[a] += 1
    count[a+1] += 1
    count[a+2] += 1
    
print(max(count))
### BUGGY CODE ###

from collections import deque
N = int(input())
T = []
for k in range(N-1):
    t = list(map(int,input().split()))
    T.append(t)


A = [-1 for k in range(N)]
A[0] = 0

while len(T) > 0:
    c = 0
    while A[T[c][0]-1] == A[T[c][1]-1] == -1:
        c += 1
    u = T[c][0]-1
    v = T[c][1]-1
    w = T[c][2] 
    T.pop(c)
    if w%2 == 0:
        if A[u] == 0 and A[v] == -1:
            A[v] = 0
        elif A[u] == 1 and A[v] == -1:
            A[v] = 1
        elif A[u] == -1 and A[v] == 0:
            A[u] = 0
        elif A[u] == -1 and A[v] == 1:
            A[u] = 1
    else:
        if A[u] == 0 and A[v] == -1:
            A[v] = 1
        elif A[u] == 1 and A[v] == -1:
            A[v] = 0
        elif A[u] == -1 and A[v] == 0:
            A[u] = 1
        elif A[u] == -1 and A[v] == 1:
            A[u] = 0

print(*A, sep="\n")

### FIXED CODE ###

N = int(input())
T = [[] for k in range(N)]
for k in range(N-1):
    u,v,w = map(int,input().split())
    T[u-1].append([v-1,w])
    T[v-1].append([u-1,w])

kyori = [-1 for k in range(N)]
kyori[T[0][0][0]] = 0
que = [T[0][0][0]]

while len(que) > 0:
    now = que.pop()
    for tsugi in T[now]:
        if kyori[tsugi[0]] == -1:
            kyori[tsugi[0]] = kyori[now] + tsugi[1]
            que.append(tsugi[0])

for a in kyori:
    print(a%2)
### BUGGY CODE ###

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

dp=[0]*(n+1)
for i in range(n,-1,-1):
  if i in a:
    dp[i] = 0
  elif i==n:
    dp[i]=1
  elif i==n-1:
    dp[i]=1
  else:
    dp[i]=dp[i+1]+dp[i+2]
    dp[i]=dp[i]%1000000007
print(dp[0])

### FIXED CODE ###

n,m=map(int,input().split())
a = [int(input()) for i in range(m)]
dp=[0]*(n+1)
if m==0:
  for i in range(n,-1,-1):
    if i==n or i==n-1:
      dp[i]=1
    else:
      dp[i]=dp[i+1]+dp[i+2]
  print(dp[0]%1000000007)
else:
  j=-1
  for i in range(n,-1,-1):
    if i==a[j]:
      if m>j*(-1):
        j-=1
    else:
      if i==n or i==n-1:
        dp[i]=1
      else:
        dp[i]=dp[i+1]+dp[i+2]
  print(dp[0]%1000000007)
### BUGGY CODE ###

import heapq
N,M = map(int,input().split())
A = list(map(int,input().split()))
B = []
C = []
for _ in range(M):
    L_,R_ = map(int,input().split())
    B.append(L_)
    C.append(R_)
heapq.heapify(A)
for i in range(M):
    for j in range(B[i]):
        tmp = heapq.heappop(A)
        if tmp >= C[i]:
            heapq.heappush(A,tmp)
            break
        heapq.heappush(A,C[i])
print(sum(A))

### FIXED CODE ###

import heapq
N,M = map(int,input().split())
A = list(map(int,input().split()))
BC = [list(map(int,input().split())) for _ in range(M)]
BC = sorted(BC,key = lambda x:x[1],reverse=True)


heapq.heapify(A)
for i in range(M):
    for j in range(BC[i][0]):
        tmp = heapq.heappop(A)
        if tmp >= BC[i][1]:
            heapq.heappush(A,tmp)
            break
        heapq.heappush(A,BC[i][1])
print(sum(A))
### BUGGY CODE ###

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

l = []
i = 2
while p > 1:
    if p % i == 0:
        p //= i
        l.append(i)
    else:
        i += 1
        if i > p:
            break
        
ans = 1

for i in set(l):
    m = l.count(i)
    if n <= m:
        ans *= i ** (m // n)

print(ans)

### FIXED CODE ###

n, p = map(int, input().split())
if n == 1:
    print(p)
    exit()
l = []
i = 2
while p > 1:
    if p % i == 0:
        p //= i
        l.append(i)
    else:
        i += 1
        if i > p ** (1/2):
            break
        
ans = 1

for i in set(l):
    m = l.count(i)
    if n <= m:
        ans *= i ** (m // n)

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

#JOI
def main():
    X=input()
    Y=input()
    dp=[[0 for y in range(1+len(Y))] for x in range(1+len(X))]
    for x in range(len(X)):
        for y in range(len(Y)):
            now=0
            dp[x][y]=max(dp[x-1][y],dp[x][y-1])
            for x1 in range(Y[:y+1].count(X[x])):
                idx=now+Y[now:y+1].index(X[x])
                now=idx+1
                dp[x][y]=max(dp[x-1][idx-1]+1,dp[x][y])
            now=0
            for y1 in range(X[:x+1].count(Y[y])):
                idx=now+X[now:x+1].index(Y[y])
                now=idx+1
                dp[x][y]=max(dp[idx-1][y-1]+1,dp[x][y])
    print(dp[len(X)-1][len(Y)-1])
for i in range(int(input())):
    main()


### FIXED CODE ###

def main():
    X=input()
    Y=input()
    dp=[]
    for y in range(len(Y)):
        now=0
        for i  in range(len(dp)):
            d=dp[i]
            if Y[y] in X[now:d]:
                dp[i]=now+X[now:d].index(Y[y])
            now=d+1
        if Y[y] in X[now:]:
            dp.append(now+X[now:].index(Y[y]))
    return len(dp)
for i in range(int(input())):
    print(main())
### BUGGY CODE ###

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 2*10**6
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

r1,c1,r2,c2 = map(int, input().split())
ans = cmb(r2+c2+2,c2+1,mod)-cmb(r2+c1+1,c1,mod)-cmb(r1+c2+1,c2+1,mod)+cmb(r1+c1,c1,mod)
print(ans)

### FIXED CODE ###

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 2*10**6+10
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

r1, c1, r2, c2 = map(int, input().split())

def g(r, c):
  return cmb(r+c+2,c+1,mod)-1

ans = g(r2,c2)-g(r2,c1-1)-g(r1-1,c2)+g(r1-1,c1-1)
print(ans%mod)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

n = int(input())
a = [0] * n
for i in range(n):
    a[i] = int(input())

cnt = 0
lit = 0

while lit != 1 and (lit != 0 or cnt == 0):
    lit = a[lit] - 1
    cnt += 1

if lit == 1:
    print(cnt)
else:
    print(-1)


### FIXED CODE ###

N = int(input())
A = [int(input()) for _ in range(N)]
i = 0
done = {a - 1: False for a in A}
num = 0
while True:
    i = A[i] - 1
    num += 1
    if i == 1:
        print(num)
        exit()
    if done[i]:
        print(-1)
        exit()
    done[i] = True
### BUGGY CODE ###

def main():
	N, M = map(int, input().split())
	A = []
	B = []
	for i in range(N):
		a, b = map(int, input().split())
		A.append(a)
		B.append(b)
	cost = 0
	while True:
		mc = 0
		minp = min(A)
		for i in range(N):
			if A[i] == minp:
				mc = B[i]
				A[i] = 10**10
		if M <= mc:
			for i in range(mc):
				M -= 1
				cost += minp
				if M <= 0:
					print(cost)
					return
		else:
			M -= mc
			cost += minp * mc
	return

if __name__ == '__main__':
	main()


### FIXED CODE ###

def main():
	N, M = map(int, input().split())
	S = []
	for i in range(N):
		a, b = map(int, input().split())
		S.append([a, b])
	sorted_shop_list = sorted(S, key=lambda x: x[0])
	cost = 0
	for i in sorted_shop_list:
		a = i[0]
		b = i[1]
		if b < M:
			M -= b
			cost += a * b
		else:
			cost += a * M
			break
	print(cost)
	return

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

N = int(input())
S = []
for i in range(N):
  S.append(input())
T = list(set(S))
number = [] 
for i in range(len(T)):
  number.append(S.count(T[i]))
maxindex = [i for i, x in enumerate(number) if x == max(number)]
Ans = []
for i in range(len(maxindex)):
  Ans.append(T[maxindex[i]])
Ans.sort()
for i in Ans:
  print(i)

### FIXED CODE ###

N = int(input())
S = [input() for _ in range(N)]
dictionary = {}
for word in S:
  if word in dictionary:
    dictionary[word] += 1 #辞書の中にその言葉があったら、keyを+1
  else:
    dictionary[word] = 1#無いなら、その言葉を登録して,keyを1にする
maximum = max(dictionary.values()) #辞書のkeyの最大値を返す
for key,value in sorted(dictionary.items()): #keyとvalueの両方に対してfor文
  if value == maximum:
    print(key)
### BUGGY CODE ###

n = int(input())
s = 0
cnt = 1
while True:
    s += cnt
    if s < n <= s+cnt+1:
        use = cnt+1
        sub = use*(use+1)//2 - n
        for i in range(use):
            if i+1 == sub:
                continue
            print(i+1)
        exit()
    else:
        cnt += 1


### FIXED CODE ###

n = int(input())
if n == 1:
    print(1)
    exit()
s = 0
cnt = 1
while True:
    s += cnt
    if s < n <= s+cnt+1:
        use = cnt+1
        sub = use*(use+1)//2 - n
        for i in range(use):
            if i+1 == sub:
                continue
            print(i+1)
        exit()
    else:
        cnt += 1
### BUGGY CODE ###

import sys	

num1 = list(map(int, input().split()))
N = num1[0] #参加者数
K = num1[1] #初期ポイント
Q = num1[2] #出た正解の数
ans_list = []
for index1 in range(Q):
	ans_list.append(int(input()))
for index1 in range(1,N+1):
	point = 0
	for index2 in range(Q):
		if index1==ans_list[index2]:
			point +=1

	fin=K+point-Q

	
	if fin <=0:
		print("No")
	else:
		print("Yes")
		

### FIXED CODE ###

N, K, Q = map(int,input().split())
point_list = [0 for i in range(N+1)]
for i in range(Q):
    A = int(input())
    point_list[A]+=1
for i in range(1,N+1):
    if point_list[i]+K-Q<=0:
        print("No")
    else:
        print("Yes")
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def combination(n, r, mod):
    numerator, denominator = 1, 1
    for _ in range(r):
        numerator = numerator * n % mod
        denominator = denominator * r % mod
        n -= 1
        r -= 1
    return numerator * pow(denominator, mod - 2, mod) % mod

mod = 10**9 + 7


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

A.sort()
sum_max = 0
for i in range(k - 1, n):
    sum_max += A[i] * combination(i, k - 1, mod)

A.sort(reverse = True)
sum_min = 0
for i in range(k - 1, n):
    sum_min += A[i] * combination(i, k - 1, mod)

print((sum_max - sum_min) % mod)


### FIXED CODE ###

import sys
input = sys.stdin.readline

mod = 10**9 + 7


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

FACTORIAL = [1] * (n + 1)
for i in range(1, n + 1):
    FACTORIAL[i] = FACTORIAL[i - 1] * i % mod
INVERSE = [1] * (n + 1)
INVERSE[n] = pow(FACTORIAL[n], mod - 2, mod)
for i in range(n - 1, -1, -1):
    INVERSE[i] = INVERSE[i + 1] * (i + 1) % mod

def combination(n, r):
    return FACTORIAL[n] * INVERSE[n - r] % mod * INVERSE[r] % mod

A.sort()
sum_max = 0
for i in range(k - 1, n):
    sum_max = (sum_max + A[i] * combination(i, k - 1)) % mod

A.sort(reverse = True)
sum_min = 0
for i in range(k - 1, n):
    sum_min = (sum_min + A[i] * combination(i, k - 1)) % mod

print((sum_max - sum_min) % mod)
### BUGGY CODE ###

k=int(input())
cur=1
ans=[]
while len(ans)<k:
    num=str(cur)
    n=len(num)
    flag=True
    pos=-1
  #  print(num,end=' num\n')
    for i in range(n-1):
        if abs(int(num[i])-int(num[i+1]))>1:
            pos=i+1
            flag=False
            break
 #   print(flag)
    if flag==True:
        ans.append(cur)
        cur+=1
    else:
        if int(num[pos])!=9:
            ch=str(int(num[pos])+1)
#            print(ch)
            cur=int(num[:pos]+ch+num[pos+1:])
        else:
            ch=str(int(num[pos-1])+1)
            cur=int(num[:pos-1]+ch+'0'*len(num[pos:]))
print(ans[-1])


### FIXED CODE ###

k=int(input())
cur=1
ans=-1
cnt=0
while cnt<k:
    num=str(cur)
    n=len(num)
    flag=True
    pos=-1
  #  print(num,end=' num\n')
    for i in range(n-1):
        if abs(int(num[i])-int(num[i+1]))>1:
            pos=i+1
            flag=False
            break
 #   print(flag)
    if flag==True:
        ans=cur
        cur+=1
        cnt+=1
    else:
        if int(num[pos])!=9:
            ch=str(int(num[pos])+1)
#            print(ch)
            cur=int(num[:pos]+ch+num[pos+1:])
        else:
            ch=str(int(num[pos-1])+1)
            cur=int(num[:pos-1]+ch+'0'*len(num[pos:]))
print(ans)
### BUGGY CODE ###

h,w=map(int,input().split())
m=[]
for _ in range(h): m.append(list(input()))
black=0
white=0
for i in range(h):
    for j in range(w):
        if m[i][j]=="#": black+=1
white=h*w-black
node=[[0,0,1]]
dx,dy=[-1,0,1,0],[0,1,0,-1]
while node:
    temp=node.pop(0)
    if temp[0]==h-1 and temp[1]==w-1:
        print(h*w-black-temp[2])
        exit()
    m[temp[0]][temp[1]]="#"
    for i in range(4):
        if 0<=temp[0]+dx[i]<h and 0<=temp[1]+dy[i]<w:
            if m[temp[0]+dx[i]][temp[1]+dy[i]]==".":
                node.append([temp[0]+dx[i],temp[1]+dy[i],temp[2]+1])
print(-1)           

### FIXED CODE ###

h,w=map(int,input().split())
m=[]
for _ in range(h): m.append(list(input()))
black=0
white=0
for i in range(h):
    for j in range(w):
        if m[i][j]=="#": black+=1
white=h*w-black
node=[[0,0,1]]
dx,dy=[-1,0,1,0],[0,1,0,-1]
while node:
    temp=node.pop(0)
    if temp[0]==h-1 and temp[1]==w-1:
        print(h*w-black-temp[2])
        exit()
    m[temp[0]][temp[1]]="#"
    for i in range(4):
        if 0<=temp[0]+dx[i]<h and 0<=temp[1]+dy[i]<w:
            if m[temp[0]+dx[i]][temp[1]+dy[i]]==".":
                node.append([temp[0]+dx[i],temp[1]+dy[i],temp[2]+1])
                m[temp[0]+dx[i]][temp[1]+dy[i]]="#"
print(-1)