Harryxun/stf_run huggingface dataset:
def chess(h,w):
    o = ""
    for i in range(h):
        for j in range(w):
            if (i+j)%2: o+="."
            else: o+="#"
        o+="\n
 
while 1:
    h,w=map(int,raw_input().split())
    if h==w==0:break
    chess(h,w)

### FIXED CODE ###

def chess(h,w):
    o = ""
    for i in range(h):
        for j in range(w):
            if (i+j)%2: o+="."
            else: o+="#"
        o+="\n"
    print o
 
while 1:
    h,w=map(int,raw_input().split())
    if h==w==0:break
    chess(h,w)
n = int(input())
lst = []
STATUS = "Good"
while n > 0:
    lst.append(n%10)
    n //= 10 # 必須
lst.reverse()
for i in range(3):
  if lst[i] == lst[i + 1]:
    STATUS = "Bad"
  else:
    pass
print(STATUS)

### FIXED CODE ###

n = str(input())
lst = []
STATUS = "Good"
lst = list(map(int, n))
for i in range(3):
  if lst[i] == lst[i + 1]:
    STATUS = "Bad"
  else:
    pass
print(STATUS)
n, m = map(int, input().split())
import math
pn = math.factorial(n) / (math.factorial(n-2) * math.factorial(2))
pm = math.factorial(m) / (math.factorial(m-2) * math.factorial(2))
print(pn + pm)

### FIXED CODE ###

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

p = n * (n - 1) // 2 + m * (m - 1) // 2

print(p)
import copy
H,W=map(int,input().split())


MAP=[["." for i in range (W)]for i in range(H)]
LIST=[0]*10**6

l=0
r=0
for i in range(H):
    A=list(input())
    for j in range(W):
        if(A[j]=="#"):
            LIST[r]=(i,j,0)
            r+=1

while(True):
    T=LIST[l]
    i=T[0]
    j=T[1]
    if(i>0):
        if(MAP[i-1][j]=="."):
            MAP[i-1][j]="#"
            LIST[r]=(i-1,j,T[2]+1)
            r+=1  
    if(i+1<H):
        if(MAP[i+1][j]=="."):
            MAP[i+1][j]="#"
            LIST[r]=(i+1,j,T[2]+1)
            r+=1  
    if(j>0):
        if(MAP[i][j-1]=="."):
            MAP[i][j-1]="#"
            LIST[r]=(i,j-1,T[2]+1)
            r+=1  
    if(j+1<W):
        if(MAP[i][j+1]=="."):
            MAP[i][j+1]="#"
            LIST[r]=(i,j+1,T[2]+1)
            r+=1
    l+=1
    if(r<=l):
        print(LIST[r-1][2])
        exit()  



### FIXED CODE ###

H,W=map(int,input().split())

MAP=[["." for i in range (W)]for i in range(H)]
LIST=[0]*(10**6+100)

l=0
r=0
for i in range(H):
    A=list(input())
    for j in range(W):
        if(A[j]=="#"):
            MAP[i][j]="#"
            LIST[r]=(i,j,0)
            r+=1

while(True):
    T=LIST[l]
    i=T[0]
    j=T[1]
    if(i>0):
        if(MAP[i-1][j]=="."):
            MAP[i-1][j]="#"
            LIST[r]=(i-1,j,T[2]+1)
            r+=1  
    if(i+1<H):
        if(MAP[i+1][j]=="."):
            MAP[i+1][j]="#"
            LIST[r]=(i+1,j,T[2]+1)
            r+=1  
    if(j>0):
        if(MAP[i][j-1]=="."):
            MAP[i][j-1]="#"
            LIST[r]=(i,j-1,T[2]+1)
            r+=1  
    if(j+1<W):
        if(MAP[i][j+1]=="."):
            MAP[i][j+1]="#"
            LIST[r]=(i,j+1,T[2]+1)
            r+=1
    l+=1
    if(r<=l):
        print(LIST[r-1][2])
        exit()
import math
N = int(input())
A = [int(i) for i in input().split()]

num = 1

if len(A) == 2:
  print(max(A))
else:
  for i in range(len(A)):
    B = A[ : i] + A[i + 1:]
    g = reduce(math.gcd, B)
    if (g > num):
      num = g
  print num


### FIXED CODE ###

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

n = t // a
print(n * b)
s=input()
  
if s =  "Sunny":
	print("Cloudy")
elif s = "Cloudy":
	print("Rainy")
else:
	print("Sunny")

### FIXED CODE ###

s=input()

if s ==  "Sunny":
	print("Cloudy")
elif s == "Cloudy":
	print("Rainy")
else:
	print("Sunny")
class Dice(object):
 
    def __init__(self, d):

        self.rows = [d[0], d[4], d[5], d[1]]
        self.cols = [d[0], d[2], d[5], d[3]]
 
    def __move_next(self, x, y):
        temp = y.pop(0)
        y.append(temp)
        x[0] = y[0]
        x[2] = y[2]
 
    def __move_prev(self, x, y):
        temp = y.pop(3)
        y.insert(0, temp)
        x[0] = y[0]
        x[2] = y[2]
 
    def execute(self, c):
        for i in self.c:
            self.__move(i, self.rows, self.cols)
 
    def __move(self, com, x, y):
        if com == "N":
            self.__move_prev(y, x)
        elif com == "S":
            self.__move_next(y, x)
        elif com == "E":
            self.__move_prev(x, y)
        elif com == "W":
            self.__move_next(x, y)
 
    def print_top(self):
        print(self.rows[0])
    
    def execute2(self, a, b):

        while self.rows[0] == b:
           self.__move_next(self.rows, self.cols)
        
        while self.rows[0] == a and self.rows[1] == b:
            self.__move_next(self.cols, self.rows)
    
    def print_right_side(self):
        print(self.cols[4])
        

d = map(int, input().split(" "))
c = input() 
dice = Dice2(d)

for i in range(c):
    a, b = map(int, input().split(" "))
    dice.execute2(a,b)
    dice.print_right_side()



### FIXED CODE ###

class Dice(object):
 
    def __init__(self, d):

        self.rows = [d[0], d[4], d[5], d[1]]
        self.cols = [d[0], d[2], d[5], d[3]]
 
    def __move_next(self, x, y):
        temp = y.pop(0)
        y.append(temp)
        x[0] = y[0]
        x[2] = y[2]
 
    def __move_prev(self, x, y):
        temp = y.pop(3)
        y.insert(0, temp)
        x[0] = y[0]
        x[2] = y[2]
 
    def execute(self, c):
        for i in c:
            self.__move(i, self.rows, self.cols)
 
    def __move(self, com, x, y):
        if com == "N":
            self.__move_prev(y, x)
        elif com == "S":
            self.__move_next(y, x)
        elif com == "E":
            self.__move_prev(x, y)
        elif com == "W":
            self.__move_next(x, y)
 
    def print_top(self):
        print(self.rows[0])
    
    def execute2(self, a, b):
        self.__rot(a)
        if a == self.rows[0] or a == self.rows[2]:
            self.__move_prev(self.cols, self.rows)    
        
        self.__rot(b)
        
        while a != self.rows[0]:
            self.__move_prev(self.cols, self.rows)    
        
        if b == self.rows[1]:
            print(self.cols[3])
        elif b == self.rows[3]:
            print(self.cols[1])
        
    def __rot(self, z):
        i = 0
        while z not in self.rows:
            self.__move_next(self.rows, self.cols)
            if i > 3:
                self.__move_next(self.cols, self.rows)
                i = 0
            i+=1

d = list(map(int, input().split(" ")))
c = int(input()) 
dice = Dice(d)

for i in range(c):
    a, b = map(int, input().split(" "))
    dice.execute2(a,b)
import sys
A = input()
N = len(A)
B = [0] * len(A)
k = 0
tmp= 0
for i in range(len(A)):
    if A[i] == 'R':
        tmp += 1
        for j in range(i+1,N):
            if A[j] == 'R':
                tmp += 1
            else:
                k = j
                break
        if tmp % 2 ==0:
            B[k] += 1
        else:
            B[k-1] += 1
        tmp = 0
    else:
        tmp += 1
        for j in range(1,i)[::-1]:
            if A[j] == 'L':
                tmp += 1
            else:
                k = j
                break
        if tmp % 2 ==0:
            B[k] += 1
        else:            
            B[k+1] += 1
        tmp = 0
L = [str(i) for i in B]
print(" ".join(L))


### FIXED CODE ###

import sys,fractions
a = input()
n = len(a)
t = []
ans = [0] * n
cnt = 0
tmp = a[0]
for i in range(n):
    if a[i] == tmp:
       cnt += 1 
    else:
        t.append(cnt)
        tmp = a[i]
        cnt = 1
t.append(cnt)
N = len(t)
len = 0
for i in range(N)[::2]:
    tmp_len = t[i] + t[i+1]
    #R
    ans[len + t[i] - 1] += int((t[i]+1)/2)
    ans[len + t[i]] += int(t[i]/2)
    #L
    ans[len + t[i] - 1] += int(t[i+1]/2)
    ans[len + t[i]] += int((t[i+1]+1)/2)
    len += tmp_len
L = [str(i) for i in ans]
print(" ".join(L))
nums = input().split()
print(nums[0] * nums[1])

### FIXED CODE ###

nums = input().split()
print(int(nums[0]) * int(nums[1]))
from bisect import bisect_left
import sys
sys.setrecursionlimit(1000000)



def dfs(p):
    ai = a[p]
    i = bisect_left(dp, ai)
    old = dp[i]
    dp[i] = ai
    ans[p] = bisect_left(dp, INF)-1
    for child in to[p]:
        if ans[child] is None:
            dfs(child)
    dp[i] = old
    
    
        

if __name__ == "__main__":
    n = int(input())
    a = [None] + list(map(int, input().split()))
    to = [[] for _ in range(n+1)]
    for _ in range(n-1):
        u, v = map(int, input().split())
        to[u].append(v)
        to[v].append(u)
    INF = 10**20
    dp = [INF]*(n+1)
    dp[0]= -INF
    q = deque([1])
    ans = [None]*(n+1)
    dfs(1)
    print("\n".join(list(map(str, ans[1:]))))

### FIXED CODE ###

from bisect import bisect_left
import sys
sys.setrecursionlimit(1000000)



def dfs(p):
    ai = a[p]
    i = bisect_left(dp, ai)
    old = dp[i]
    dp[i] = ai
    ans[p] = bisect_left(dp, INF)-1
    for child in to[p]:
        if ans[child] is None:
            dfs(child)
    dp[i] = old
    
    
        

if __name__ == "__main__":
    n = int(input())
    a = [None] + list(map(int, input().split()))
    to = [[] for _ in range(n+1)]
    for _ in range(n-1):
        u, v = map(int, input().split())
        to[u].append(v)
        to[v].append(u)
    INF = 10**20
    dp = [INF]*(n+1)
    dp[0]= -INF
    ans = [None]*(n+1)
    dfs(1)
    print("\n".join(list(map(str, ans[1:]))))
N,K = map(int,input().split())
H = [int(i) for i in input().split()]

dp = [10**10]*N
dp[0] = 0
for i in range(1,K):
  for j in range(0,i):
    dp[i] = min(dp[i],dp[j]+abs(H[i]-H[j]))
for i in range(K,N):
  for j in range(i-K,i):
    dp[i] = min(dp[i],dp[j]+abs(H[i]-H[j]))
print(dp[-1])


### FIXED CODE ###

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

K=min(K,N-1)
dp = [10**10]*N
dp[0] = 0
for i in range(1,K):
  for j in range(0,i):
    dp[i] = min(dp[i],dp[j]+abs(H[i]-H[j]))
for i in range(K,N):
  for j in range(i-K,i):
    dp[i] = min(dp[i],dp[j]+abs(H[i]-H[j]))
print(dp[-1])
import sys
s =sys.stdin.readlines()
N,C = map(int,s[0].split())
D = [[int(i) for i in sys[1+j].split()] for j in range(C)]
c = [[int(i) for i in sys[C+j].split()] for j in range(N)]

D_sum = [[0]*C for _ in range(3)]

for i in range(C):
    for j in range(N):
        for k in range(N):
            D_sum[(j+k)%3][i] += D[c[j][k]-1][i]
            
ans = 1000*500*500
for i in range(C):
    for j in range(C):
        for k in range(C):
            if i==j or j==k or k==i:
                continue
            else:
                ans = min(ans, D_sum[0][i]+D_sum[1][j]+D_sum[2][k])
print(ans)      


### FIXED CODE ###

N,C = map(int,input().split())
D = [[int(i) for i in input().split()] for j in range(C)]
c = [[int(i) for i in input().split()] for j in range(N)]

c_sum = [[0]*C for _ in range(3)]
for i in range(N):
    for j in range(N):
        c_sum[(i+j)%3][c[i][j]-1] += 1

D_sum = [[0]*C for _ in range(3)]
for i in range(C):
    for j in range(C):
        for k in range(3):
            D_sum[k][j] += D[i][j] * c_sum[k][i]

ans = 1000*500*500
for i in range(C):
    for j in range(C):
        for k in range(C):
            if i==j or j==k or k==i:
                continue
            else:
                ans = min(ans, D_sum[0][i]+D_sum[1][j]+D_sum[2][k])
print(ans)
N2 = N
sum = 0
while True:
    sum += N % 10
    N = N // 10
    if N == 0:
        break
if N2 % sum == 0:
    print('Yes')
else:
    print('No')


### FIXED CODE ###

# coding: utf-8
# Your code here!
N = int(input())
N2 = N
sum = 0
while True:
    sum += N % 10
    N = N // 10
    if N == 0:
        break
if N2 % sum == 0:
    print('Yes')
else:
    print('No')
a=list(input())
if sort(a)==[a,b,c]:
  print('Yes')
else:
  print('No')


### FIXED CODE ###

a=input()
if len(set(a))==3:
  print('Yes')
else:
  print('No')
n=int(input())
p=[list(map(int,input().split()))for i in range(n)]
if n==1:
  print(p[0][0],p[0][1],p[0][2])
else:
  for i in range(0,101):
    for j in range(0,101):
      k=1
      l=p[0][2]+abs(i-p[0][0])+abs(j-p[0][1])
      for x,y,h in p:
        m=h+abs(i-x)+abs(j-y)
        if l!=m:
          k=0
      if k:
        ans=[i,j,l]
  print(ans[0],ans[1],ans[2])


### FIXED CODE ###

n=int(input())
p=[list(map(int,input().split()))for i in range(n)]
d=[]
for i in range(n):
  if p[i][2]==0:
    d.append(i)
d.sort(reverse=1)
for i in d:
  del p[i]
if len(p)==1:
  print(p[0][0],p[0][1],p[0][2])
else:
  for i in range(0,101):
    for j in range(0,101):
      k=1
      l=p[0][2]+abs(i-p[0][0])+abs(j-p[0][1])
      for x,y,h in p:
        if h==0:
          continue
        m=h+abs(i-x)+abs(j-y)
        if l!=m:
          k=0
      if k:
        ans=[i,j,l]
  print(ans[0],ans[1],ans[2])
import math
def main():
    h = int(input())
    cnt = 0
    ans = 0
    tmp = 1
    a = int(math.log2(h))
    cnt = 2 **a
    ans = (1-2**(a+1))//(1-2)
    print(ans)

if __name__=='__main__':
    main()


### FIXED CODE ###

import math
def main():
    h = int(input())
    cnt = 0
    ans = 0
    tmp = 1
    a = int(math.log2(h))
    cnt = 2 **a
    ans = (1-2**a)//(1-2)
    print(ans+cnt)
    
if __name__=='__main__':
    main()
n = int(input())
a = [int(i) for i in input().split()]

# aの各数値の個数をdictで保持(数値:個数) 
a_dict = {}
for v in a:
    if v in a_dict:
        a_dict[v] += 1
    else:
        a_dict[v] = 1

# a_dictの中になければならない数値のリストを作成
possible_list = {i: True for i in range(1, n, 2)}
 
can = True
if n % 2 == 0:
    for k, v in a_dict.items():
        # 数値が2個でない、もしくはkがpossible_list内に存在しないならFalse
        if v != 2 or k not in possible_list:
            can = False
            break
else:
　　　　if a_dict[0] != 1:
        can = Falsen = int(input())
a = [int(i) for i in input().split()]

# aの各数値の個数をdictで保持(数値:個数) 
a_dict = {}
for v in a:
    if v in a_dict:
        a_dict[v] += 1
    else:
        a_dict[v] = 1

# a_dictの中になければならない数値のリストを作成(0以外)
 
if n % 2 == 0:
    possible_list = {i: True for i in range(1, n, 2)}
    for k, v in a_dict.items():
        # 2個でない、もしくはpossible_list内に存在しない数値ならFalse
        if v != 2 or k not in possible_list:
            print(0)
            exit()
else:
    possible_list = {i: True for i in range(0, n, 2)}
    if a_dict[0] != 1:
        print(0)
        exit()
    else:
        a_dict[0] = 2
        for k, v in a_dict.items():
            if v != 2 or k not in possible_list:
                print(0)
                exit()
 
print(2 ** (n // 2) % (10 ** 9 + 7))
    else:
        for k, v in a_dict.items():
            if v != 2 or k not in possible_list:
                can = False
                break
 
if can:
    print(2 ** (n // 2) % (10 ** 9 + 7))
else:
    print(0)

### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()]

a_dict = {}
for v in a:
    if v in a_dict:
        a_dict[v] += 1
    else:
        a_dict[v] = 1

 
if n % 2 == 0:
    possible_list = {i: True for i in range(1, n, 2)}
    for k, v in a_dict.items():
        if v != 2 or k not in possible_list:
            print(0)
            exit()
else:
    possible_list = {i: True for i in range(0, n, 2)}
    if a_dict[0] != 1:
        print(0)
        exit()
    else:
        a_dict[0] = 2
        for k, v in a_dict.items():
            if v != 2 or k not in possible_list:
                print(0)
                exit()
 
print(2 ** (n // 2) % (10 ** 9 + 7))
a, b = int(input().split())
if a*b % 2 == 1:
    print('Odd')
else:
    print('Even')

### FIXED CODE ###

a, b = map(int, input().split())
if a*b % 2 == 1:
    print("Odd")
else:
    print("Even")
N = int(input())
print('Yes' if 9 in N else 'No')

### FIXED CODE ###

N = input()
print('Yes' if '9' in N else 'No')
N=int(input())
print(['No','Yes'][9 in [N%10, (N-N%10)//10]]

### FIXED CODE ###

N=int(input())
print(['No','Yes'][9 in [N%10, (N-N%10)//10]])
import numpy

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

if 0 in num:
    print(0)
elif len([i for i in num if i >= 10**18]) != 0:
    print(-1)
else:
    mult = numpy.prod(num)
    if mult > 10**18:
        print(-1)
    else:
        print(mult)

### FIXED CODE ###

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

limit = 10 ** 18
A.sort()
result = A[0]
for a in A[1:]:
    result *= a
    if result > limit:
        print(-1)
        exit()
print(result)
import copy

N, Q = map(int, input().split())
S = input()
t = [0]*N
for i in range(N):
    t[i+1] = t[i] + (1 if S[i:i+2] == "AC" else 0)

for i in range(Q):
    l, r = map(int, input().split())
    print(t[r-1]-t[l-1])




### FIXED CODE ###

import copy

N, Q = map(int, input().split())
S = input()
t = [0]*(N+1)
for i in range(N):
    t[i+1] = t[i] + (1 if S[i:i+2] == "AC" else 0)

for i in range(Q):
    l, r = map(int, input().split())
    print(t[r-1]-t[l-1])
N = int(input())
d_(i+1) = [ int(input()) for i in range(N)]
sum = 0
for i in range(N):
    for j in range range(i-1):
        sum = sum + d_i * d_j
print(sum)

### FIXED CODE ###

N = int(input())
d = list(map(int,input().split()))
sum = 0
for i in range(N):
    if i > 0:
        for j in range(i):
            sum = sum + d[i] * d[j]
print(sum)
data = list(map(int, input()))

_sum = sum(data)

print( 15-_sum )

### FIXED CODE ###

data = list(map(int, input().split()))

_sum = sum(data)

print( 15-_sum )
N = int(input())
data = [list(map(int,input().split())) for i in range(N)]
mod = 10**9+7
ans = 0

from math import gcd

A = []

for i in range(N):
    if data[i][0] == 0 and data[i] == 0:  #(0,0)の場合は以降取り除いて考える
        ans += 1
    else:                                 #各々の成分をgcdで割り、第1成分が非負になるように調整
        if data[i][0] < 0:
            data[i][0] *= -1
            data[i][1] *= -1
        g = gcd(data[i][0],data[i][1])
        data[i][0] //= g
        data[i][1] //= g
        if data[i][0] == 0:
            A.append((0,1))
        elif data[i][1] > 0:
            A.append((data[i][0],data[i][1]))
        elif data[i][1] == 0:
            A.append((1,0))
        else:
            A.append((data[i][0],data[i][1]))


from collections import Counter

C = Counter(A)
D = []             #仲が悪いイワシの数の組

for i,j in list(C.keys()):
    if j <= 0:
        continue
    else:
        if j == 0:
            if C[(0,1)] > 0:
                D.append((C[(1,0)],C[(0,1)]))
        else:
            if C[(j,-i)] > 0:
                D.append((C[(i,j)],C[(j,-i)]))

r = 0  #仲が悪くなり得るイワシの数
for i,j in D:
    r += i+j

a = 1  #仲が悪くなり得るイワシたちの選び方
for i,j in D:
    a = (a*(pow(2,i,mod)+pow(2,j,mod)-1)) % mod

a = (a*pow(2,len(A)-r,mod)) % mod  #仲が悪くなり得ないイワシたちの選び方

ans += a-1  #全部選ばないものを除く

print(ans)

### FIXED CODE ###

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

from math import gcd

A = []

for i in range(N):
    if data[i][0] == 0 and data[i][1] == 0:  #(0,0)の場合は以降取り除いて考える
        ans += 1
    else:                                 #各々の成分をgcdで割り、第1成分が非負になるように調整
        if data[i][0] < 0:
            data[i][0] *= -1
            data[i][1] *= -1
        g = gcd(data[i][0],data[i][1])
        data[i][0] //= g
        data[i][1] //= g
        if data[i][0] == 0:
            A.append((0,1))
        elif data[i][1] == 0:
            A.append((1,0))
        else:
            A.append((data[i][0],data[i][1]))


from collections import Counter

C = Counter(A)
D = []             #仲が悪いイワシの数の組

for i,j in list(C.keys()):
    if j <= 0:
        continue
    else:
        if j == 0:
            if C[(0,1)] > 0:
                D.append((C[(1,0)],C[(0,1)]))
        else:
            if C[(j,-i)] > 0:
                D.append((C[(i,j)],C[(j,-i)]))

r = 0  #仲が悪くなり得るイワシの数
for i,j in D:
    r += i+j

a = 1  #仲が悪くなり得るイワシたちの選び方
for i,j in D:
    a = (a*(pow(2,i,mod)+pow(2,j,mod)-1)) % mod

a = (a*pow(2,len(A)-r,mod)) % mod  #仲が悪くなり得ないイワシたちの選び方

ans += a-1  #全部選ばないものを除く

print(ans % mod)
s=list(input())
for i in range(s):
	if s[i]==1:
    	s[i]=9
    else:
    	s[i]=1

### FIXED CODE ###

s=list(input())
for i in range(3):
    if s[i]=="1":
        s[i]=9
    else:
        s[i]=1
print(s[0]*100+s[1]*10+s[2])
mod = 10 ** 9 + 7
N = 1000

#逆元テーブル
inv_t = [0]+[1]
for i in range(2, N):
  inv_t += [inv_t[mod % i] * (mod - int(mod / i)) % mod]

#階乗計算
kai = [1, 1]
rev_kai = [1, inv_t[1]]
for i in range(2, N):
	kai.append(kai[-1] * i % mod)
	rev_kai.append(rev_kai[-1] * inv_t[i] % mod)

# コンビネーション計算
def cmb(n, r):
	return kai[n] * rev_kai[r] * rev_kai[n-r] % mod

if __name__ == '__main__':
	n, r = map(int, input().split())
	print(cmb(n, r))


### FIXED CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7
a.sort(reverse = True)

N = n+2
P = mod
inv_t = [0]+[1]
for i in range(2,N):
  inv_t += [inv_t[P % i] * (P - int(P / i)) % P]

base = 1
for item in range(n-k+1, n):
    base = (base * item) % mod
for i in range(1, k):
    base = (base * inv_t[i]) % mod
base2 = base

ans = 0
ans2  = 0
top = n - 1
for ai in a:
    if top < k-1:
        break
    if ai > 0:
        ans += base * ai
        ans %= mod
    else:
        ans2 += abs(base * ai)
        ans2 %= mod

    base = base * inv_t[top] * (top - k + 1)  % mod
    top -= 1

top = n-1
for ai in reversed(a):
    if top < k-1:
        break
    if ai > 0:
        ans2 += base2 * ai
        ans2 %= mod
    else:
        ans += abs(base2 * ai)
        ans %= mod
    base2 = base2 * inv_t[top] * (top - k + 1)  % mod
    top -= 1
print((ans - ans2) % mod)
import math
 
N=int(input())
if N%1000==0:
  print(0)
else:
  N=(math.ceil(money/1000))*1000-N
  print(int(N))


### FIXED CODE ###

n = int(input())

if n % 1000 == 0:
  print(0)
else:
  print(1000-(n%1000))
def e_friendships(N, K):
    if K > (N - 1) * (N - 2) // 2:
        return -1

    ans_graph = []
    for i in range(2, N + 1):
        ans_graph.append('{} {}'.format(1, i))  # スターの構成

    def append_edge(t, lst=[]):
        count = 0
        for i in range(2, N):
            for j in range(i + 1, N + 1):
                if count == t:
                    return lst
                lst.append('{} {}'.format(i, j))
                count += 1

    ans_graph = append_edge((N - 1) * (N - 2) // 2 - K, ans_graph)
    return str(len(ans_graph)) + '\n' + '\n'.join(ans_graph)

N, K = [int(i) for i in input().split()]
print(e_friendships(N, K))

### FIXED CODE ###

def e_friendships(N, K):
    if K > (N - 1) * (N - 2) // 2:
        return -1

    ans_graph = []
    for i in range(2, N + 1):
        ans_graph.append('{} {}'.format(1, i))  # スターの構成

    def append_edge(t, lst=[]):
        count = 0
        for i in range(2, N):
            for j in range(i + 1, N + 1):
                if count == t:
                    return lst
                lst.append('{} {}'.format(i, j))
                count += 1
        return lst

    ans_graph = append_edge((N - 1) * (N - 2) // 2 - K, ans_graph)
    return str(len(ans_graph)) + '\n' + '\n'.join(ans_graph)

N, K = [int(i) for i in input().split()]
print(e_friendships(N, K))
import numpy as np
n, m, c = map(int, input().split())
b = np.array(list(map(int, input().split())))
ans = 0
for i in range(n) :
	a = np.array(list(map(int, input().split())))
	if np.sum(a * b) + c > 0 :
		ans += 1
print(ans)

### FIXED CODE ###

n, m, c = map(int, input().split())
b = list(map(int, input().split()))
ans = 0
for i in range(n) :
	a = list(map(int, input().split()))
	if sum([x * y for (x, y) in zip(a, b)]) + c > 0 :
		ans += 1
print(ans)
a = int(input())

print(round(a*a*a+a*a+a)

### FIXED CODE ###

a = int(input())

print(round(a*a*a+a*a+a))
a, b = map(int, input().split(' '))
print(floor((a + b)/2))

### FIXED CODE ###

a, b = map(int, input().split(' '))
import math
print(math.ceil((a + b)/2))
l = map(int,raw_input().split())
L = sorted(l,key=int)
print str(L[0]),str(L[1]),str(L[2])

### FIXED CODE ###

l=list(map(int,input().split()))
L=sorted(l)
print(L[0],L[1],L[2])