Harryxun/stf_run huggingface dataset:
import sys
sys.setrecursionlimit=10**12

def modinv(a,m=10**9+7):
    if a==0: return 1
    else:
        b=m
        (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 % m

def cur(p):
    for x in neighbor[p]:
        par[x]=p
        neighbor[x].remove(p)
        if x>0 and x<=n: descend[p]+=cur(x)
    return descend[p]

def cur2(p):
    for x in neighbor[p]:
        ans[x]=ans[p]*descend[x]*modinv(n-descend[x])
        ans[x]%=mod
        cur2(x)

mod=10**9+7
n=int(input())
neighbor=[set()  for _ in range(n+1)]
descend=[1]*(n+1)
par=[-1]+[0]*n

for _ in range(n-1):
    a,b=map(int,input().split())
    neighbor[a].add(b)
    neighbor[b].add(a)
cur(1)


ans=[1]*(n+1)
ans1=1
for i in range(1,n+1):
    ans1=ans1*i*modinv(descend[i])
    ans1%=mod
ans[1]=ans1

cur2(1)

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

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)

def modinv(a,m=10**9+7):
    if a==0: return 1
    else:
        b=m
        (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 % m

def cur(p):
    if neighbor[p]==[]: return
    for x in neighbor[p]:
        par[x]=p
        neighbor[x].remove(p)
        cur(x)
    descend[par[p]]+=descend[p]

def cur2(p):
    for x in neighbor[p]:
        ans[x]=ans[p]*descend[x]*modinv(n-descend[x])
        ans[x]%=mod
        cur2(x)

mod=10**9+7
n=int(input())
neighbor=[set()  for _ in range(n+2)]
descend=[1 for i in range(n+1)]
par=[0]+[0]*(n+1)

for _ in range(n-1):
    a,b=map(int,input().split())
    neighbor[a].add(b)
    neighbor[b].add(a)

cur(1)


ans=[1]*(n+1)
ans1=1
for i in range(1,n+1):
    ans1=ans1*i*modinv(descend[i])
    ans1%=mod
ans[1]=ans1

cur2(1)

for i in range(1,n+1):
    print(ans[i])
def ncr(n, r):
    ans = 1
    if r * 2 >= n:
        return ncr(n, n - r)
    for i in xrange(n - r + 1, n + 1):
        ans *= i
    for i in xrange(1, r + 1):
        ans //= i
    return ans


def main():
    n, p = [int(_) for _ in raw_input().split()]
    o = 0
    e = 0
    for ai in (int(_) for _ in raw_input().split()):
        if ai % 2 == 1:
            o += 1
        else:
            e += 1
    t = 2 ** e
    ans = 0
    for q in xrange(p, o + 1, 2):
        ans += t * ncr(o, q)
    return ans


if __name__ == '__main__':
    print(main())


### FIXED CODE ###

def ncr(n, r):
    ans = 1
    if r * 2 > n:
        return ncr(n, n - r)
    for i in xrange(n - r + 1, n + 1):
        ans *= i
    for i in xrange(1, r + 1):
        ans //= i
    return ans


def main():
    n, p = [int(_) for _ in raw_input().split()]
    o = 0
    e = 0
    for ai in (int(_) for _ in raw_input().split()):
        if ai % 2 == 1:
            o += 1
        else:
            e += 1
    t = 2 ** e
    ans = 0
    for q in xrange(p, o + 1, 2):
        ans += t * ncr(o, q)
    return ans


if __name__ == '__main__':
    print(main())
a, b, k = map(int, input().split())

ans = []

for i in range(1, max(a, b)):
 	if a % i == 0 and b % i == 0:
		ans.append(i)

print(ans[-k])




### FIXED CODE ###

a, b, k = map(int, input().split())

ans = []

for i in range(1, max(a, b) + 1):
	if a % i == 0 and b % i == 0:
		ans.append(i)

print(ans[-k])
def ii():return int(input())
def iim():return map(int,input().split())
def iil():return list(map(int,input().split()))
from collections import deque


def bfs(xg,yg):
    queue = deque([(xs,ys,0)])
    while queue:
        x,y,dep = queue.popleft()
        l = []
        for xx,yy in [(1,0),(0,1),(-1,0),(0,-1)]:
            for i in range(1,k+1):
                nx,ny = x+xx*i,y+yy*i
                if cord[ny][nx] == '.':
                    l.append((nx,ny))
                elif cord[ny][nx] < dep+1:
                    break
        for nx, ny in l:
            if cord[ny][nx] == '.':
                cord[ny][nx] = dep+1
                if (nx,ny) == (xg,yg):
                    return dep+1
                else:
                    queue.append((nx,ny,dep+1))
    return -1

h,w,k = iim()
ys,xs,yg,xg = iim()

cord = [['@']*(w+2)]
for i in range(h):
    cord.append(['@']+list(input())+['@'])
cord.append(['@']*(w+2))
cord[ys][xs] = '#'

print(bfs(xg,yg))


### FIXED CODE ###

def ii():return int(input())
def iim():return map(int,input().split())
def iil():return list(map(int,input().split()))
from collections import deque


def bfs(xg,yg):
    queue = deque([(xs,ys,0)])
    while queue:
        x,y,dep = queue.popleft()
        l = []
        f1 = True
        f2 = True
        f3 = True
        f4 = True
        for i in range(1,k+1):
            if f1:
                if cord[y][x+i] == '.':
                    l.append((x+i,y))
                elif cord[y][x+i] == '@' or cord[y][x+i] != dep+1:
                    f1 = False
            if f2:
                if cord[y][x-i] == '.':
                    l.append((x-i,y))
                elif cord[y][x-i] == '@' or cord[y][x-i] != dep+1:
                    f2 = False
            if f3:
                if cord[y+i][x] == '.':
                    l.append((x,y+i))
                elif cord[y+i][x] == '@' or cord[y+i][x] != dep+1:
                    f3 = False
            if f4:
                if cord[y-i][x] == '.':
                    l.append((x,y-i))
                elif cord[y-i][x] == '@' or cord[y-i][x] != dep+1:
                    f4 = False
            if not (f1 or f2 or f3 or f4):
                break
        for nx, ny in l:
            if cord[ny][nx] == '.':
                cord[ny][nx] = dep+1
                if (nx,ny) == (xg,yg):
                    return dep+1
                else:
                    queue.append((nx,ny,dep+1))
    return -1

h,w,k = iim()
ys,xs,yg,xg = iim()

cord = [['@']*(w+2)]
for i in range(h):
    cord.append(['@']+list(input())+['@'])
cord.append(['@']*(w+2))
cord[ys][xs] = '#'
#for i in cord:
#    print(*i)
#print(len(cord),len(cord[0]))

print(bfs(xg,yg))
H, W = map(int, input().split())
sw = [list(str(input())) for i in range(H)]
dx = [1,0,-1,0]
dy = [0,1,0,-1]

for i in range(H):
  for j in range(W):
    if sw[i][j] == "#":
      counter = 0
      for k in range(4):
        if i+dx[k] < 0 or i+dx[k] >= H or j+dy[k] < 0 or j+dy[k] >= H:
          counter += 1
        elif sw[i+dx[k]][j+dy[k]] == ".":
          counter += 1
      if counter == 4:
        print("No")
        exit()
print("Yes")

### FIXED CODE ###

H, W = map(int, input().split())
s = [list(input()) for i in range(H)]
check = [[False]*W]*H
dx = -1,0,1,0
dy = 0,-1,0,1

for h in range(H):
  for w in range(W):
    bcount = 0 #隣接する黒ますの個数
    if s[h][w] == "#":
      for i in range(4):
        if 0 <= h+dx[i] <= H-1 and 0 <= w+dy[i] <= W-1 and s[h+dx[i]][w+dy[i]] == "#":
            bcount += 1
      if bcount == 0:
        print("No")
        exit()
print("Yes")
N = int(input())
lst = []
for i in range(N):
  for j in range(int(input())):
    lst.append(list(map(int,input().split())))
ans = 0
for i in range(2**N):
  flag = True
  bin_lst = list(bin(i)[2:].zfill(N))
  for idx,j in enumerate(bin_lst):
    if (j == '1'):
      for v, w in zip(lst[idx][:-1],lst[idx][1:]):
        if (bin_lst[v-1] != str(w)):
          flag = False
  if (flag):
    ans = max(ans,bin_lst.count('1'))
print(ans)


### FIXED CODE ###

N = int(input())
lst = [[] for i in range(N)]
for i in range(N):
  for j in range(int(input())):
    lst[i].append(list(map(int,input().split())))
ans = 0
for i in range(2**N):
  flag = True
  bin_lst = list(bin(i)[2:].zfill(N))
  for idx,j in enumerate(bin_lst):
    if (j == '1'):
      for v, w in lst[idx]:
        if (bin_lst[v-1] != str(w)):
          flag = False
  if (flag):
    ans = max(ans,bin_lst.count('1'))
print(ans)
n = int(input())
x = [int(w) for w in input().split()]

d = {}

for i in x:
    d[i] = d.get(i, 0) + 1
    
ans = 0
l = list(d.keys())
l = sorted(l)
#print(l)
for i in range(len(l)-2):
    for j in range(i+1, len(l)-1):
        for k in range(j+1, len(l)):
            if l[k] < l[i] + l[j]:
                #print(l[i], l[j], l[k])
                ans += d[l[i]]*d[l[j]]*d[l[k]]
            
            else:
                break
            
print(ans)

### FIXED CODE ###

x, k, d = map(int, input().split())
x = abs(x)

t = float(abs(x/d))

 
if t >= k:
    print(abs(x - (k*d)))
    
elif (k-int(t))%2==0:
    print(abs(x-abs(int(t)*d)))
    
else:
    print(abs(x-abs(int(t)*d)-d))
nums = input(),split()
a = int(nums[0])
b = int(nums[1])
c = int(nums[2])
if a < b < c:
    print(a, b, c)
elif a =< b=< c:
    print(a, b, c)
elif a > b > c:
    print(a, b, c)
elif a >= b => c:
    print(a, b, c)

### FIXED CODE ###

nums = input().split()
a = int(nums[0])
b = int(nums[1])
c = int(nums[2])
if a <= b <= c:
    print(a, b, c)
elif a <= c <= b:
    print(a, c, b)
elif b <= a <= c:
    print(b, a, c)
elif b <= c <= a:
    print(b, c, a)
elif c <= a <= b:
    print(c, a, b)
else:
    print(c, b, a)
s = input().split()
if A > 10 or B > 10:
  print(1)
else:
  print(A * B)

### FIXED CODE ###

a = list(map(int,input().split()))
if a[0] >= 10 or a[1] >= 10:
  print('-1')
else:
  print(a[0] * a[1])
i_r = input()
print(i_r * i_r)

### FIXED CODE ###

i_r = int(input())
print(i_r * i_r)
N, K = map(int, input().split())
h = list(map(int, input().split()))

memo = [-1 for _ in range(N)]

def dp(n):
  if memo[n] != -1:
    return memo[n]
  elif n != 0:
    m = min([dp(n-i)+abs(h[n]-h[n-i]) for i in range(1, min(K, n)+1)])
    memo[n] = m
    return m
  else:
    memo[n] = 0
    return memo[n]

for n in range(N-1):
  dp(n)
print(dp(N-1))

### FIXED CODE ###

import sys

sys.setrecursionlimit(1000000)

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

memo = [10**10 for _ in range(N+1)]

def dp(i):
    if i == 1:
        return 0
    elif i == 2:
        memo[i] = abs(h[i-2]-h[i-1])
        return memo[i]
    elif memo[i] < 10**10:
        return memo[i]
    else:
        memo[i] = min(
            dp(i-1) + abs(h[i-2]-h[i-1]),
            dp(i-2) + abs(h[i-3]-h[i-1]),
            dp(i-2) + abs(h[i-3]-h[i-2]) + abs(h[i-2]-h[i-1])
        )
        return memo[i]
print(dp(N))
A,B,C=map(int, input().split())
d = [0 0 0]
d[0] = abs(A-B)
d[1] = abs(A-C)
d[2] = abs(C-B)
d.sort()
print(d[0]+d[1])


### FIXED CODE ###

A,B,C=map(int, input().split())
d = [0,0,0]
d[0] = abs(A-B)
d[1] = abs(A-C)
d[2] = abs(C-B)
d.sort()
print(d[0]+d[1])
n,k=map(int,input().split())
s=input()
a=[]
a.append(0)
tmp=1
for i in range(len(s)-1):
	if s[i] != s[i+1]:
		a.append(i+1)
a.append(n)

#print(a)

if len(a)==2:
	print(a[1])
else:
	if s[0]=='0':
		m=2*k
	else:
		m=2*k+1
	if m>len(s):
		print(len(s))
	else:
		_max=a[m]
		i=1
		while m+i<len(a):
			tmp=a[i+m]-a[i]
			#print(tmp)
			if tmp>_max:
				_max=tmp
			i+=1
		print(_max)


### FIXED CODE ###

n,k=map(int,input().split())
s=input()
a=[]
a.append(0)
for i in range(len(s)-1):
	if s[i] != s[i+1]:
		a.append(i+1)
a.append(n)
if s[-1]=='0':
	m=2*k
else:
	m=2*k+1
t=4*k+1
_max=0
i=len(a)-1
if i- m<0:
	print(n)
else:
	while i-m>=0:
		tmp=a[i]-a[i-m]
		#print('i:{} tmp:{}'.format(i,tmp))
		if tmp>_max:
			_max=tmp
		m=t-m
		i-=1
	if a[i]>_max:
		_max=a[i]
	print(_max)
import sys
input = sys.stdin.readline
# import numpy as np

S = input().rstrip()

MOD = 10 ** 9 + 7
n = len(S)

# dp = np.zeros((100005, 13), dtype=np.uint64)

list1 = [[0]*100005]*13

dp[0][0] = 1

for i in range(n):
    if S[i] == '?':
        c = -1
    else:
        c = int(S[i])
    
    for j in range(10):
        if c != -1 and c != j:
            continue
        for ki in range(13):
            dp[i+1][(ki * 10 + j) %13] += dp[i][ki]
            
    for j in range(13):
        dp[i+1][j] %= MOD
        
    res = dp[n][5]
    
print(res)

### FIXED CODE ###

import sys
input = sys.stdin.readline
# import numpy as np

S = input().rstrip()

MOD = 10 ** 9 + 7
n = len(S)

# dp = np.zeros((100005, 13), dtype=np.uint64)

dp = [[0 for i in range(13)] for j in range(100005)]

dp[0][0] = 1

for i in range(n):
    if S[i] == '?':
        c = -1
    else:
        c = int(S[i])
    
    for j in range(10):
        if c != -1 and c != j:
            continue
        for ki in range(13):
            dp[i+1][(ki * 10 + j) %13] += dp[i][ki]
            
    for j in range(13):
        dp[i+1][j] %= MOD
        
        
    res = dp[n][5]
    
print(res)
a,b = int(input())

if a*b % 2 == 0:
  print('Even')
else a*b % 2 == 1:
  print("Odd")

### FIXED CODE ###

a, b = map(int, input().split())
if (a*b) % 2:
    print("Odd")
else:
    print("Even")
alice = 0
bob = 0
n = int(input())
a = sorted(list(map(int, input().split(' ')))).reverse()

for i in a[::2]: alice += i
for i in a[1::2]: bob += i
print(alice - bob)

### FIXED CODE ###

n = int(input())
a = int(input())
coins = 'No' if a < (n%500) else 'Yes'
print(coins)
#firsts we declare string s and k, if character s is at most with char k, it will print char s, no change
#if s i more than k it


k = int(input())
s= input()

str = s
tripledot= "..."

#if same, no change
if lens(s) == k:
         print(s)

elif len(s) > k:
         print (str[0:k],"...")


### FIXED CODE ###

#input the K and S string
#using another new variable to count the length of string
#then compare the value with the string
#if string less than the value just pring the string S
#if the length of string more than the value
#cut the string using while loop then print ... at the end
#program end

K = int(input())  #O(1)
S = input() #O(1)
value=len(S)    #O(1)

if value <= K: 
    print(S)    #O(1)
elif value > K : 
    x=0     #O(1)
    while x<K: 
        print((S[x]),end=(""))  #O(1)
        x+=1
    print("...")   #O(1)
a,b,c,d=(int(x) for x in input().split())

x = range(a,b+1)
y = range(c,d+1)

X = list(x)
Y = list(y)
MAX = max(X) * max(Y)
print(MAX)

### FIXED CODE ###

a,b,c,d = map(int, input().split())
list = [a*c, a*d, b*c, b*d]
print(max(list))
package main

import "fmt"

func main(){
	var a, b int
	for ;;{
		fmt.Scan(&a, &b)
		if a == 0 && b == 0 {
			break
		}
		fmt.Printf("%d %d\n", b, a)
	}
}


### FIXED CODE ###

import sys
input_lines = sys.stdin.readlines()[:-1]
for input_line in input_lines:
    a, b = [int(i) for i in input_line.split()]
    if a > b:
        print('{0} {1}'.format(b, a))
    else:
        print(input_line.rstrip())
import numpy as np

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

def combi(n):
    return n*(n-1)//2

"""
for i in range(n):
    count = a.count(i+1)
    count_all += combi(count)
"""
count_all = sum([combi(a.count(i+1)) for i in range(n)])
"""
for k in range(n):
    #aのk番目の要素と同じ要素の数を(k番目の要素も含めて)出し、1を引く
    count = a.count(a[k]) - 1
    ans = count_all - count
    print(ans)
"""
count = [a.count(a[k]) - 1 for k in range(n)]
x = np.array([count_all]*n)
y = np.array(count)
ans = x-y
for s in ans.tolist():
    print(s)


### FIXED CODE ###

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

ans = (n * (n-1))//2 + (m * (m-1))//2
print(ans)
n=int(input())
for i in range(n):
    a=list(map(int,input().aplit()))
    b,c=0,0
    yes = True
    for j in range(10):
        if a[j]>b:b=a[j]
        elif a[j]>c:c=a[j]
        else:yes=False
    print("YES" if yes else "NO")


### FIXED CODE ###

n=int(input())
for i in range(n):
    a=list(map(int,input().split()))
    b,c=0,0
    yes = True
    for j in range(10):
        if a[j]>b:b=a[j]
        elif a[j]>c:c=a[j]
        else:yes=False
    print("YES" if yes else "NO")
N, Q = map(int, input().split())
S = list(input())

AClist = [0]
counter = 0

i=0
while i+1 < N:
    if S[i:i+2] == "AC":
        counter+=1

    AClist.append(counter)
    i+=1


while Q > 0:
    l, r = input().split()
    r = int(r) 
    l = int(l)

    print(AClist[r-1]-AClist[l-1])

    Q -= 1





### FIXED CODE ###


b = input()

if b == "A":
  print("T")
elif b == "T":
  print("A")
elif b == "G":
  print("C")
elif b == "C":
  print("G")
dp = {100: 1, 101: 1, 102: 1, 103: 1, 104: 1, 105: 1}
l = [100, 101, 102, 103, 104, 105]
for i in range(100001):
  if i == 0:
    dp[0] = 1
  elif i < 100:
    dp[i] = 0
  elif i >= 106:
    for cost in l:
      dp[i] += dp[i-cost]

n = int(input())
if dp[n] >= 1:
  print(1)
else:
  print(0)
    

### FIXED CODE ###

dp = {100: 1, 101: 1, 102: 1, 103: 1, 104: 1, 105: 1}
l = [100, 101, 102, 103, 104, 105]
for i in range(100001):
  if i == 0:
    dp[0] = 1
  elif i < 100:
    dp[i] = 0
  elif i >= 106:
    dp[i] = 0
    for cost in l:
      dp[i] += dp[i-cost]

n = int(input())
if dp[n] >= 1:
  print(1)
else:
  print(0)
def main ():
  N = int(input())
  A = list(map(int,input(). split ()))
  if 0 in A:
    print(0)
    return
  prod = 1
  for a in A:
    prod *= a
    if prod > 1000000000000000000:
      print(-1)
      return
  print(prod)
main ()

### FIXED CODE ###

a,b= input().split()
print(int(a)*int(b))
N = int(input())
ns = input().split()

sum_ = 0

for i in range(N):
    for j in range(N):
        sum_ += int(ns[i])*int(ns[j])
        
print(sum_)

### FIXED CODE ###

a,b = input().split()
a,b = int(a),int(b)
print(max(a-2*b,0))
N =inptut()
S = map(int,imput().split())
TT = sum(TT)
T1 = 0
Ans = TT
for i in range(N):
  T1 += S[i]
  Ans = min(Ans,ABS(TT-T1-T1))
print(Ans)

### FIXED CODE ###

N =int(input())
S = list(map(int,input().split()))
TT = sum(S)
T1 = 0
Ans = TT
for i in range(N):
  T1 += S[i]
  Ans = min(Ans,abs(TT-T1-T1))
print(Ans)
# coding:utf-8
# Doubly Linked List

class DLL:

    def __init__(self):
        self.array = []

    def insert(self, x):
        self.array = [x] + self.array
    
    def delete(self, x):
        if x in dll.array:
            del self.array[self.array.index(x)]

    def deleteFirst(self):
        del self.array[0]

    def deleteLast(self):
        del self.array[len(self.array)-1]


def main():

    dll = DLL()
    n = int(input())
    ans = ""

    for _ in range(n):
        operation = input().split()
        command = operation[0]
        if command in ["insert", "delete"]:
            key = operation[1]
            eval("dll." + command + '(' + key + ')')

        else:
            eval("dll." + command + "()")
        print(dll.array)
    for value in dll.array:
        ans += str(value) + " "

    print(ans.rstrip())

if __name__ == "__main__":
    main()

### FIXED CODE ###

# coding:utf-8
# Doubly Linked List

from collections import deque

def main():

    n = int(input())
    dll = deque()

    for _ in range(n):
        operation = input().split(' ')
        if operation[0] in ["insert", "delete"]:
            key = operation[1]
            if operation[0] == "insert":
                dll.appendleft(key)
            else:
                try:
                    dll.remove(key)
                except:
                    pass

        else:
            if operation[0][6] == 'F':
                dll.popleft()

            else:
                dll.pop()

    print(' '.join(dll))

if __name__ == "__main__":
    main()
import fractions

n=int(input())
t=[]
for i in range(n):
    t.append(int(input()))

ans=t[0]*t[1]//(fractions.gcd(t[0],t[1]))
for i in range(2,n):
    ans=ans*t[i]//(fractions.gcd(ans,t[i]))
print(ans)


### FIXED CODE ###

import fractions

n=int(input())
t=[]
for i in range(n):
    t.append(int(input()))
if n>=2:
    ans=t[0]*t[1]//(fractions.gcd(t[0],t[1]))
    for i in range(2,n):
        ans=ans*t[i]//(fractions.gcd(ans,t[i]))
    print(ans)
else:
    print(t[0])
#input
import numpy as np
N, K = map(int, input().split())
A = np.array(list(map(int, input().split())))

#output
import math
A = np.sort(A)

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

q = np.full(N, 0)
for i in range(N-K+1):
    q[i] = cmb(N-i-1, N-K-i)

r = -q + q[-1::-1]

print(int((A*r).sum() % (10**9 + 7)))

### FIXED CODE ###

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

#output
import math

A.sort()
mod = 10**9+7

n_ = 10**5 + 3
fun = [1]*(n_+1)
for i in range(1,n_+1):
    fun[i] = fun[i-1]*i%mod
rev = [1]*(n_+1)
rev[n_] = pow(fun[n_],mod-2,mod)
for i in range(n_-1,0,-1):
    rev[i] = rev[i+1]*(i+1)%mod
def cmb(n,r):
    if n <= 0 or r < 0 or r > n: return 0
    return fun[n]*rev[r]%mod*rev[n-r]%mod
#これだとTLE!
"""
def cmb(n, r):
    if n < r: return 0
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result
"""

M = 0
m = 0
for i, a in enumerate(A):
    M += cmb(i, K-1) * a
    m += cmb(N-i-1, K-1) * a
    M %= mod
    m %= mod

print((M-m) % mod)
n = int(input())
A = list(map(int, input().split()))
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a%b)

if len(A) == 2:
    print(gcd(A[0], A[1]))
    exit()
b = set()
for i in range(2):
    a = 0
    for j in range(n):
        a = gcd(A[i],A[j])
        b.add(a)
b = sorted(b)
print(b[1])

### FIXED CODE ###

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

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a%b)

ans = 0
L = [0]*(n)
R = [0]*(n+1)
for i in range(n-1):
    L[i+1] = gcd(L[i], A[i])
    R[i+1] = gcd(R[i], A[-i-1])
for l, r in zip(L[::-1],R):
    ans = max(ans, gcd(l, r))
print(ans)
n,x=map(int,input().split())
m=[int(input) for _ in range(n)]
m.sort()
num=x-sum(m)
print(n+(num//min(m)))


### FIXED CODE ###

n,x=map(int,input().split())
m=[int(input()) for _ in range(n)]
m.sort()
num=x-sum(m)
print(n+(num//(min(m))))
n = input()
for i in range(6):
  if 2**i <= n and 2**(i+1) > n:
    print(2**i)
    

### FIXED CODE ###

n = input()
for i in range(7):
    if 2**i <= int(n) and 2**(i+1) > int(n):
        print(2**i)
num = input()
num_array = [i for i in num]

splits = len(num) - 1
n = 2 ** splits

sum = 0

for i in range(n):
    bin = format(i, "0{}b".format(splits))
    bin_array = [i for i in bin]
    tmp_num = str(num_array[0])
    for index, value in enumerate(bin_array):
        if value == "0":
            tmp_num += num_array[index+1]
        else:
            sum += int(tmp_num)
            tmp_num = num_array[index+1]
    sum += int(tmp_num)

print(sum)

### FIXED CODE ###


num = input()
num_array = [i for i in num]

splits = len(num) - 1
n = 2 ** splits

sum = 0

if splits > 0:
    for i in range(n):
        bin = format(i, "0{}b".format(splits))
        bin_array = [i for i in bin]
        tmp_num = str(num_array[0])
        for index, value in enumerate(bin_array):
            if value == "0":
                tmp_num += num_array[index+1]
            else:
                sum += int(tmp_num)
                tmp_num = num_array[index+1]
        sum += int(tmp_num)
else:
    sum = num

print(sum)