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

H,W=map(int, input().split())
Ch,Cw=map(int, input().split())
Dh,Dw=map(int, input().split())
A=[]
for i in range(H):
  d=list(input())
  A.append(d)
D=[[10**8]*W for i in range(H)]
DD=[[-1]*W for i in range(H)]
dy=[-1,1,0,0]
dx=[0,0,1,-1,]
ey=[2,2,2,2,2,1,1,1,1,0,0,-1,-1,-1,-1,-2,-2,-2,-2,-2]
ex=[0,1,2,-1,-2,1,2,-1,-2,2,-2,1,2,-1,-2,0,1,2,-1,-2]
for h in range(H):
  for w in range(W):
    if A[h][w]=='#':
      D[h][w]=10**5
from collections import deque
import sys
sys.setrecursionlimit(10**7) 
def bfs(y,x):
  q=deque()
  q.append((y,x))
  
  while len(q):
    y,x=q.popleft()
    cnt=0
    for i in range(4):
      ny=y+dy[i]
      nx=x+dx[i]
      if 0<=ny<H and 0<=nx<W:
        if A[ny][nx]=='.' and D[y][x]<D[ny][nx]:
          q.appendleft((ny,nx))
          D[ny][nx]=D[y][x]
          DD[ny][nx]=1

    for i in range(20):
      my=y+ey[i]
      mx=x+ex[i]
      if 0<=my<H and 0<=mx<W:
        if A[my][mx]=='.' and D[my][mx]==10**8 and DD[my][mx]==-1:
          q.append((my,mx))
          D[my][mx]=D[y][x]+1
            
D[Ch-1][Cw-1]=0
bfs(Ch-1,Cw-1)
if D[Dh-1][Dw-1]==10**8:
  print(-1)
else:
  print(D[Dh-1][Dw-1])


### FIXED CODE ###

H,W=map(int, input().split())
Ch,Cw=map(int, input().split())
Dh,Dw=map(int, input().split())
A=[]
for i in range(H):
  d=list(input())
  A.append(d)
D=[[10**8]*W for i in range(H)]
DD=[[-1]*W for i in range(H)]
dy=[-1,1,0,0]
dx=[0,0,1,-1,]
ey=[2,2,2,2,2,1,1,1,1,0,0,-1,-1,-1,-1,-2,-2,-2,-2,-2]
ex=[0,1,2,-1,-2,1,2,-1,-2,2,-2,1,2,-1,-2,0,1,2,-1,-2]
for h in range(H):
  for w in range(W):
    if A[h][w]=='#':
      D[h][w]=10**5
from collections import deque
import sys
sys.setrecursionlimit(10**7) 
def bfs(y,x):
  q=deque()
  q.append((y,x))
  
  while len(q):
    y,x=q.popleft()
    cnt=0
    for i in range(4):
      ny=y+dy[i]
      nx=x+dx[i]
      if 0<=ny<H and 0<=nx<W:
        if A[ny][nx]=='.' and D[y][x]<D[ny][nx]:
          q.appendleft((ny,nx))
          D[ny][nx]=D[y][x]
          DD[ny][nx]=1

    for i in range(20):
      my=y+ey[i]
      mx=x+ex[i]
      if 0<=my<H and 0<=mx<W:
        if A[my][mx]=='.' and D[my][mx]==10**8 and DD[my][mx]==-1:
          q.append((my,mx))
          D[my][mx]=D[y][x]+1
            
D[Ch-1][Cw-1]=0
bfs(Ch-1,Cw-1)
if D[Dh-1][Dw-1]==10**8:
  print(-1)
else:
  print(D[Dh-1][Dw-1])
### BUGGY CODE ###

#input
N = int(input())
L = list(map(int, input().split()))

#output
import heapq

L = [-l for l in L]
heapq.heapify(L)

sum = 0
while len(L) > 2:
    target = heapq.heappop(L)
    L.sort()
    for i in range(len(L)-1):
        for j in range(i+1, len(L)):
            if target > L[i] +  L[j]:
                sum += 1
        
print(sum)


### FIXED CODE ###

#input
N = int(input())
L = list(map(int, input().split()))

#output
import heapq
import bisect

L = [-l for l in L]
heapq.heapify(L)

sum = 0
while len(L) > 2:
    largest = heapq.heappop(L)
    L.sort()
    for i in range(len(L)-1):
        p = bisect.bisect_left(L, largest-L[i])
        if p-(i+1) >0:
            sum += p-(i+1)
        
print(sum)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000000)
ii = lambda: int(input())
ii0 = lambda: ii() - 1
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')

def main():
    N,M,L = mis()
    import numpy as np
    INF = np.iinfo(np.int64).max
    d = np.full((N,N), INF, dtype=np.uint64)
    for i in range(N):
        d[i,i] = 0
    #
    for _ in range(M):
        a,b,c = mis()
        a -= 1
        b -= 1
        if c <= L:
            d[a,b] = c
            d[b,a] = c
    #
    for k in range(N):
        for i in range(N):
            np.minimum(d[i,:], d[i,k]+d[k,:], out=d[i,:])    
    #
    d2 = np.full((N,N), INF, dtype=np.uint64)
    for i in range(N):
        d2[i, i] = 0
    for i in range(N):
        for j in range(N):
            if d[i, j] <= L:
                d2[i, j] = 1
    #
    for k in range(N):
        for i in range(N):
            np.minimum(d2[i,:], d2[i,k]+d2[k,:], out=d2[i,:])    
    #
    Q = ii()
    for _ in range(Q):
        s,t = mis()
        s -= 1
        t -= 1
        dist = d2[s,t]
        if dist == INF:
            print(-1)
        else:
            print(int(dist)-1)




main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000000)
ii = lambda: int(input())
ii0 = lambda: ii() - 1
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')

def main():
    N,M,L = mis()
    from scipy.sparse.csgraph import floyd_warshall
    import numpy as np
    INF = np.iinfo(np.int64).max
    d = np.full((N,N), INF, dtype=np.uint64)
    for i in range(N):
        d[i,i] = 0
    #
    for _ in range(M):
        a,b,c = mis()
        a -= 1
        b -= 1
        if c <= L:
            d[a,b] = c
            d[b,a] = c
    #
    '''
    for k in range(N):
        for i in range(N):
            np.minimum(d[i,:], d[i,k]+d[k,:], out=d[i,:])    
    '''
    d = floyd_warshall(d)
    #
    d2 = np.full((N,N), INF, dtype=np.uint64)
    for i in range(N):
        d2[i, i] = 0
    for i in range(N):
        for j in range(N):
            if d[i, j] <= L:
                d2[i, j] = 1
    #
    '''
    for k in range(N):
        for i in range(N):
            np.minimum(d2[i,:], d2[i,k]+d2[k,:], out=d2[i,:])    
    '''
    d2 = floyd_warshall(d2)
    #
    Q = ii()
    for _ in range(Q):
        s,t = mis()
        s -= 1
        t -= 1
        dist = d2[s,t]
        if dist == INF:
            print(-1)
        else:
            print(int(dist)-1)




main()
### BUGGY CODE ###

import itertools

ind = int(input())
nums = [int(x) for x in input().split()]
MOD = 1000000007
ans = 0
for v in itertools.combinations(nums, 2):
    # XOR は四則演算よりも優先度が低い…….
    ans = (ans + (v[0] ^ v[1])) % MOD

print(ans)


### FIXED CODE ###

n = int(input())
a = [int(x) for x in input().split()]
MOD = 1000000007
ans = 0
for digit in range(60):
    ones = 0
    for num in a:
        if num >> digit & 1:
            ones += 1
    zeroes = n - ones  # Zeros?
    ans = (ans + ones * zeroes * pow(2, digit, MOD)) % MOD

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

n=int(input())
from math import sqrt
for k in range(1,n+1):

    ans=0
    p=int(sqrt(k))
    for x in range(1,p+1):
        l=k-x**2
        if l<=0:
            continue

        for y in range(1,int(sqrt(k-x**2)) + 1 ):
            m=k-x**2 - y**2 -x*y
            if m<=0:
                continue
            for z in range(1,int(sqrt(m))+1):
                if z*(z+x+y)==m:
                    ans+=1
    print(ans)


### FIXED CODE ###

n=int(input())

ans=[0]*(n+1)

for x in range(1,101):
    for y in range(1,101):
        for z in range(1,101):
            f= x**2 + y**2 + z**2 + x*y + y*z + z*x
            if f<=n:
                ans[f]+=1

for i in range(1,n+1):
    print(ans[i])
### BUGGY CODE ###

S = input()
N = len(S)
sosu = 10 ** 9 + 7
dp = [[0 for i in range(13)] for j in range(N)]
j = 0
if S[j] == '?':
    flag = -1
else:
    flag = int(S[j])
if flag == -1:
    for i in range(10):
        dp[j][i] += 1
else:
    dp[j][flag] = 1
#print(dp)
for j in range(1, N):
    if S[j] == '?':
        flag = -1
    else:
        flag = int(S[j])
    for k in range(10):
        if flag == -1:
            for i in range(13):
                dp[j][(i * 10 + k) % 13] += dp[j - 1][i]
            for i in range(13):
                dp[j][i] = dp[j][i] % sosu
        else:
            for i in range(13):
                dp[j][(i * 10 + flag) % 13] = dp[j-1][i]

print(dp[N-1][5])

### FIXED CODE ###

S = input()
N = len(S)
sosu = 10 ** 9 + 7
dp = [[0 for i in range(13)] for j in range(N)]
j = 0
if S[j] == '?':
    flag = -1
else:
    flag = int(S[j])
if flag == -1:
    for i in range(10):
        dp[j][i] += 1
else:
    dp[j][flag] = 1
#print(dp)
for j in range(1, N):
    if S[j] == '?':
        flag = -1
    else:
        flag = int(S[j])
    for k in range(10):
        if flag == -1:
            for i in range(13):
                dp[j][(i * 10 + k) % 13] += dp[j - 1][i]
            for i in range(13):
                dp[j][i] = dp[j][i] % sosu
        else:
            for i in range(13):
                dp[j][(i * 10 + flag) % 13] = dp[j-1][i]
 
print(dp[N-1][5])
### BUGGY CODE ###

# F - Bracket Sequencing

N = int(input())
L = []
R = []
for _ in range(N):
    S = list(str(input()))
    sums = 0
    mins = 0
    for s in S:
        if s == '(':
            sums += 1
        else:
            sums -= 1
            mins = min(mins, sums)
    if sums >= 0:
        L.append((sums, mins))
    else:
        R.append((-sums, mins-sums))

L.sort(key=lambda x: x[1], reverse=True)
R.sort(key=lambda x: x[1], reverse=True)

ans = 'Yes'
l_now = 0
for d, min_d in L:
    if l_now + min_d < 0:
        ans = 'No'
        break
    else:
        l_now += d

r_now = 0
for d, min_d in R:
    if r_now + min_d < 0:
        ans = 'No'
        break
    else:
        r_now += d

if l_now != r_now:
    ans = 'No'

print(ans)

### FIXED CODE ###

# F - Bracket Sequencing

N = int(input())
L = []
R = []
for _ in range(N):
    S = list(str(input()))
    len_S = len(S)
    L_d = 0
    L_min_d = 0
    R_d = 0
    R_min_d = 0
    for i in range(len_S):
        if S[i] == '(':
            L_d += 1
        else:
            L_d -= 1
            L_min_d = min(L_min_d, L_d)
        if S[len_S-i-1] == ')':
            R_d += 1
        else:
            R_d -= 1
            R_min_d = min(R_min_d, R_d)
    if L_d >= 0:
        L.append((L_d, L_min_d))
    else:
        R.append((R_d, R_min_d))

L.sort(key=lambda x: x[1], reverse=True)
R.sort(key=lambda x: x[1], reverse=True)

ans = 'Yes'
l_now = 0
for d, min_d in L:
    if l_now + min_d < 0:
        ans = 'No'
        break
    else:
        l_now += d

r_now = 0
for d, min_d in R:
    if r_now + min_d < 0:
        ans = 'No'
        break
    else:
        r_now += d

if l_now != r_now:
    ans = 'No'

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

P=10**9+7
def egcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)
def inv(x):
    return egcd(x,P)[0]
N=int(input())
Fact=[0 for i in range(N+1)]
Finv=[0 for i in range(N+1)]
Fact[0]=1
Finv[0]=1
for i in range(N):
    Fact[i+1]=((i+1)*Fact[i])%P
    Finv[i+1]=(Finv[i]*inv(i+1))%P
SGN=[0 for i in range(N)]
ans=0
for k in range(N):
    if 2*k-N>=0:
        SGN[k]=(((Fact[k-1]*Fact[k])%P)*Finv[2*k-N])%P
        ans=(ans+k*(SGN[k]-SGN[k-1]))%P
print(ans)


### FIXED CODE ###

P=10**9+7
def egcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)
def inv(x):
    return egcd(x,P)[0]
N=int(input())
Fact=[0 for i in range(N+1)]
Finv=[0 for i in range(N+1)]
Fact[0]=1
Finv[0]=1
for i in range(N):
    Fact[i+1]=((i+1)*Fact[i])%P
    Finv[i+1]=(Finv[i]*inv(i+1))%P
SGN=[0 for i in range(N)]
ans=0
for k in range(N):
    if 2*k-N>=0:
        SGN[k]=(((Fact[k-1]*Fact[k])%P)*Finv[2*k-N])%P
        ans=(ans+k*(SGN[k]-SGN[k-1]))%P
print(ans)
### BUGGY CODE ###

from functools import reduce
from operator import mul

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

p_score = reduce(mul, a[:k])
answers = []
for i in range(k, n):
    answers.append(a[i-k] < a[i])
for ans in answers:
    if ans:
        print("Yes")
    else:
        print("No")


### FIXED CODE ###

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

answers = []
for i in range(k, n):
    answers.append(a[i-k] < a[i])
for ans in answers:
    if ans:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

def getinputdata():

    array_result = []    
    array_result.append(input().split(" "))

    flg = True

    try:
        while flg:

            data = input()

            if(data != ""):
                
                array_result.append(data.split(" "))

                flg = True

            else:

                flg = False
    finally:

        return array_result

arr_data = getinputdata()

n= int(arr_data[0][0])

arr=[int(arr_data[1][x]) for x in range(n)]

arr = [i for i in arr if i % 2==0]

cnt=0

while len(arr)>0:
    
    if any(x % 4 == 0 for x in arr):

        val=max(list(filter(lambda x : x%4 ==0, arr)))        
        idx=arr.index(val)

        arr=[x*3 for x in arr]
        arr[idx]//=6
        cnt+=1

#    elif any(x % 2 == 0 for x in arr):
    else:
        cnt+=len(arr)
        break

print(cnt)




### FIXED CODE ###

def getinputdata():

    array_result = []    
    array_result.append(input().split(" "))

    flg = True

    try:
        while flg:

            data = input()

            if(data != ""):
                
                array_result.append(data.split(" "))

                flg = True

            else:

                flg = False
    finally:

        return array_result

arr_data = getinputdata()

n= int(arr_data[0][0])

arr=[int(arr_data[1][x]) for x in range(n)]
arr01 = [x for x in arr if x % 4 ==0] 
arr02 = [x for x in arr if x % 4 !=0 and x % 2==0] 

cnt=0
if len(arr)>0:

    for i in arr01:

        while i % 2==0:

            i//=2
        
            cnt+=1
    
    cnt+=len(arr02)
   
print(cnt)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N=int(input())
A=[list(map(int,input().split())) for i in range(N)]
mod=10**9+7

#bitDP
DPLIST=[-1]*(2**N)
DPLIST[2**N-1]=1

def dp(NOW,x):

    if DPLIST[NOW]!=-1:
        return DPLIST[NOW]

    ANS=0

    for i in range(N):
        if A[x][i]==1 and NOW & (1<<i) ==0:
            ANS+=dp(NOW+2**i,x+1)

    ANS%=mod
    DPLIST[NOW]=ANS
    return ANS

print(dp(0,0)%mod)

### FIXED CODE ###

import sys
input = sys.stdin.readline

N=int(input())
A=[list(map(int,input().split())) for i in range(N)]
mod=10**9+7

#bitDP
DPLIST=[-1]*(2**N)
DPLIST[2**N-1]=1

def dp(NOW,x):

    if DPLIST[NOW]!=-1:
        return DPLIST[NOW]

    ANS=0

    for i in range(N):
        if A[x][i]==1 and NOW & (1<<i) ==0:
            ANS+=dp(NOW+(1<<i),x+1)

    ANS%=mod
    DPLIST[NOW]=ANS
    return ANS

print(dp(0,0))
### BUGGY CODE ###

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

count = 0
for i in range(n):
    for j in range(n):
        if i > j:
            for k in range(n):
                    if j > k:
                        if k != i and k != j:
#                             print(l_list[i], l_list[j], l_list[k])
                            if (l_list[i] < l_list[j] + l_list[k]) and (l_list[j] < l_list[i] + l_list[k]) and (l_list[k] < l_list[i] + l_list[j]):
                                count += 1
print(count)

### FIXED CODE ###

N=int(input())
L_list = list(map(int,input().split()))

import bisect

L_list = sorted(L_list)
 
ans = 0
for a_index in range(0, N):
    for b_index in range(a_index+1, N):
        a = L_list[a_index]
        b = L_list[b_index]
        c_right_index = bisect.bisect_left(L_list, a+b)
        if c_right_index > b_index:
            ans += c_right_index - b_index - 1
        else:
            pass

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

import collections
N,M=map(int,input().split())
L=[]
R=[]
for i in range(M):
  l,r=[int(i) for i in input().split()]
  L.append(l)
  R.append(r)
LR=[]
for i in range(M):
  for j in range(L[i],R[i]+1):
    LR.append(j)
LR=collections.Counter(LR)
LR=LR.most_common()
LR=dict(LR)
cnt=0
for i in list(LR.values()):
  if i==M:
    cnt+=1
print(cnt)

### FIXED CODE ###

N,M=map(int,input().split())
L=[]
R=[]
for i in range(M):
  l,r=[int(i) for i in input().split()]
  L.append(l)
  R.append(r)
Lmax=max(L)
Rmin=min(R)
if Rmin-Lmax>=0:
  print(Rmin-Lmax+1)
else:
  print(0)
### BUGGY CODE ###

import fractions
n=int(input())
a=list(map(int,input().split()))
ans=1
for i in range(n):
    ai=a[:i]+a[i+1:]
    while len(ai)>1:ai.append(fractions.gcd(ai.pop(),ai.pop()))
    ans=max(ans,ai[0])
print(ans)

### FIXED CODE ###

import fractions
n=int(input())
a=list(map(int,input().split()))
l=[a[0]]
for i in range(1,n):
    l.append(fractions.gcd(l[-1],a[i]))
    if l[-1]==1:
        for j in range(n-len(l)):l.append(1)
        break
r=[a[-1]]
for i in range(n-2,-1,-1):
    r.append(fractions.gcd(r[-1],a[i]))
    if r[-1]==1:
        for j in range(n-len(r)):r.append(1)
        break
r=r[::-1]
ans=max(l[-2],r[1])
for i in range(1,n-1):ans=max(ans,(fractions.gcd(l[i-1],r[i+1])))
print(ans)
### BUGGY CODE ###

N = int(input())
S = input()
hdg_chg_nrs = []
for i in range(len(S)):
    hdg_chg = S[0:i].count('W') + S[i+1:N].count('E')
    hdg_chg_nrs.append(hdg_chg)
print(min(hdg_chg_nrs))


### FIXED CODE ###

N = int(input())
S = input()
hdg = S[1:N].count('E')
hdg_chgd = hdg
hdg_chg_nrs =[]
for i in range(1,N):
    if S[i] == 'E':
        hdg_chgd -= 1
    if S[i-1] == 'W':
        hdg_chgd += 1
    hdg_chg_nrs.append(hdg_chgd)
hdg_chgd_f = min(hdg_chg_nrs)
print(min(hdg, hdg_chgd_f))
### BUGGY CODE ###

n=int(input())
l=sorted(list(map(int, input().split())))
ans=0
x=[]
for i in range(n):
    for j in range(i+1,n):
        for k in range(j+1,(n-sum((x>l[j]+l[i]) for x in l))):
            if (l[i]<(l[j]+l[k])and l[j]<(l[i]+l[k]) and l[k]<(l[j]+l[i]) and x.count([l[i],l[j],l[k]])==0):
                x.append([l[i],l[j],l[k]])
                ans+=1

print(ans)

### FIXED CODE ###

def triangles(a): 
    n = len(a) 
    a.sort() 
    count = 0
    for i in range(0,n-2):
        k=i+2
        for j in range(i+1,n): 
            while (k < n and a[i] + a[j] > a[k]): 
                k += 1
            if(k>j): 
                count += k - j - 1
    return count
n=int(input())
a=list(map(int,input().split()))
print(triangles(a))
### BUGGY CODE ###

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

cnt = 0
for i in range(len(lst)):
    num = lst[i]
    r_lst = sorted(lst[:i+1])

    if num == r_lst[0]:
        cnt += 1

print(cnt)


### FIXED CODE ###

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

cnt = 0
tmp_min = max(lst)
for i in range(len(lst)):
    num = lst[i]
    if num <= tmp_min:
        cnt += 1
        tmp_min = num

print(cnt)
### BUGGY CODE ###

"""
ジャガー「わからん」
先にmax,minそれぞれの和を求める
"""

import sys
input = sys.stdin.readline

mod = 10**9+7

def getComb(n, k, MOD):
    if n < k:
        return 0
    if n-k < k:
        k = n-k
    # n!/(n-k)!
    comb = 1
    for x in range(n-k+1, n+1):
        comb = (comb * x) % MOD
    # k!
    d = 1
    for x in range(1, k+1):
        d = (d * x) % MOD
    # n!/((n-k)!*k!)
    comb *= pow(d, MOD-2, MOD)
    return comb % MOD

def main():
    N,K = map(int,input().split())
    A = sorted([int(i) for i in input().split()])

    cmb = [0] * (N-K+1)
    for i in range(N-K+1):
        cmb[i] = getComb(i+(K-1),K-1,mod)

    sum_min = 0
    sum_max = 0
    for i in range(N):
        if i >= K-1:
            sum_max = (sum_max + (cmb[i-(K-1)] * A[i]) % mod) % mod
        if i <= N-K: 
            sum_min = (sum_min + (cmb[(N-K)-i] * A[i]) % mod) % mod
        
    answer = (sum_max - sum_min) % mod
    print(answer)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

def getComb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p


N,K = map(int,input().split())
A = sorted([int(i) for i in input().split()])

# ref: https://www.planeta.tokyo/entry/5195/
mod = 10**9+7
fact = [1, 1]
factinv = [1, 1] 
inv = [0, 1]
for i in range(2,N+1):
    fact.append((fact[-1] * i) % mod)
    inv.append((-inv[mod % i] * (mod // i)) % mod)
    factinv.append((factinv[-1] * inv[-1]) % mod)

cmb = [0] * (N-K+1)
for i in range(N-K+1):
    cmb[i] = getComb(i+(K-1),K-1,mod)

sum_max = 0
for i in range(K-1,N):
    sum_max = (sum_max + cmb[i-(K-1)] * A[i]) % mod

sum_min = 0
for i in range(N-K,-1,-1):
    sum_min = (sum_min + cmb[(N-K)-i] * A[i]) % mod

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

import sys
input = sys.stdin.readline

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

m = 1
for i in AS:
    m = m * i

if m > 10**18:
    print(-1)
else:
    print(m)

### FIXED CODE ###

import sys
input = sys.stdin.readline

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

m = 1
j = 0

if 0 in AS:
    print(0)
    j = 1
    

if j == 0:
    for i in AS:
        m = m * i
        if m > 10**18 and j == 0:
            print(-1)
            j = 1
            break
        elif m == 0:
            break
        else:
            continue

if j == 0:
    print(m)
### BUGGY CODE ###

import math

n, d, a = map(int,input().split())
xh = []
for i in range(n):
    x,h = map(int,input().split())
    xh.append([x,h])

num = 0
xh.sort(key=lambda xh:xh[0])
l = len(xh)
dam = [0]*n
rang = [0]*n
for i in range(n):
    rang[i] = xh[i][0]-d
    
for i in range(n):
    res = xh[i][1]-dam[i]
    if res > 0:
        nat = math.ceil(res/a)
        pos = xh[i][0]+d
        num += nat
        for j in range(i+1,n):
            if rang[j] <= pos:
                dam[j] += a*nat
            else:
                break
print(num)


### FIXED CODE ###

import math

n, d, a = map(int,input().split())
xh = [[0 for i in range(2)] for j in range(n)]
left = [i for i in range(n)]
for i in range(n):
    x,h = map(int,input().split())
    xh[i] = [x,h]

num = 0
xh.sort(key=lambda xh:xh[0])

for i in range(n):
    for j in range(left[i-1],i):
        if xh[j][0]+d >= xh[i][0]-d:
            left[i] = j
            break

dam = [0]*n

def dsum(k):
    if k == 0:
        return 0
    elif left[k] == 0:
        return dam[k-1]
    else:
        return dam[k-1]-dam[left[k]-1]

for i in range(n):
    res = xh[i][1]-dsum(i)
    nat = max([math.ceil(res/a),0])
    dam[i] = dam[i-1]+a*nat
    if res > 0:
        num += nat

print(num)
### BUGGY CODE ###

n = int(input())
l = [2, 1]
i = 2
a = 0
while True:
    a = l[i-1]+l[i-2]
    l.append(a)
    if i == n: break
    i+=1
print(a)

### FIXED CODE ###

n = int(input())
a = []
a.append(2)
a.append(1)
for i in range(2, n+1):
    a.append(a[i-2]+a[i-1])
print(a[n])
### BUGGY CODE ###

N,K = map(int,input().split())
from collections import Counter
a = list(map(int,input().split()))
c = Counter(a)
ks = 0
if len(c.keys()) <= K:print(0)
else:
    for i in range(K):

        ks += c.most_common()[i][1]
    print(N-ks)

### FIXED CODE ###

N,K = map(int,input().split())
A = list(map(int, input().split()))
from collections import Counter

values = Counter(A).values()
length = len(values)
values = sorted(values)
ANS = 0

for i in range(length - K):
  ANS += values[i]
print(ANS)
### BUGGY CODE ###

s = input()
q = int(input())

for i in range(q):
    a = input()
    if a[0] == "1":
        s = s[::-1]
    elif a[0] == "2":
        if a[2] == "1":
            s = a[4] + s
        elif a[2] == "2":
            s = s + a[4]

print(s)


### FIXED CODE ###

s = input()
q = int(input())

x = []
y = []
cnt = 0

for i in range(q):
    a = list(input().split())
    if a[0] == "1":
        x, y = y, x
        cnt += 1
    else:
        if a[1] == "1":
            x.append(a[2])
        else:
            y.append(a[2])

if cnt % 2 == 1:
    s = s[::-1]

s = ''.join(x[::-1]) + s + ''.join(y)

print(s)
### BUGGY CODE ###

ans=0
a,b=map(int,input().split())
for s in range(a+1):
    for t in range(a+1):
        for r in range(a+1):
            ans+=(b-s-t-r==0)
print(ans)

### FIXED CODE ###

ans=0
a,b=map(int,input().split())
for s in range(a+1):
    for t in range(a+1):
        if 0<=b-s-t<=a:
            ans+=1
print(ans)