Harryxun/stf_run huggingface dataset:
# coding: utf-8
import sys
from heapq import heapify, heappop, heappush

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# 同じ地点で銀貨の枚数によって別の状態として扱う（最大max(A)*(N-1))
N, M, S = lr()
UVAB = [lr() for _ in range(M)]
CD = [lr() for _ in range(N)]  # 0-indexed
Amax = 0
for i in range(M):
    a = UVAB[i][2]
    if a > Amax:
        Amax = a

limit = Amax*(N-1)
graph = [[] for _ in range(N+1)] # 1-indexed
for u, v, a, b in UVAB:
    graph[u].append((v, a, b))
    graph[v].append((u, a, b))

def dijkstra(start):
    # 時間、銀貨の枚数、現在地をqueへ
    INF = 10 ** 15
    dist = [[INF for _ in range(limit+1)] for _ in range(N+1)]
    dist[1][S] = 0
    que = [(0, S, 1)]
    while que:
        time, silver, prev = heappop(que)
        if dist[prev][silver] < time:
            continue
        for next, a, b in graph[prev]:
            t = time + b
            si = silver - a
            if si < 0:
                continue
            if dist[next][si] > t:
                dist[next][si] = t
                heappush(que, (t, si, next))
        c, d = CD[prev-1]
        si = min(limit, silver+c)
        while dist[prev][si] > time + d:
            dist[prev][si] = time + d
            heappush(que, (time+d, si, prev))
            si += c; si = min(limit, si)
            time += d
            
    return dist

dist = dijkstra(1)
for i in range(2, N+1):
    d = dist[i]
    answer = min(d)
    print(answer)

# 52

### FIXED CODE ###

# coding: utf-8
import sys
from heapq import heapify, heappop, heappush

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# 同じ地点で銀貨の枚数によって別の状態として扱う（最大max(A)*(N-1))
N, M, S = lr()
UVAB = [lr() for _ in range(M)]
CD = [lr() for _ in range(N)]  # 0-indexed
Amax = 0
for i in range(M):
    a = UVAB[i][2]
    if a > Amax:
        Amax = a

limit = Amax*(N-1)
S = min(S, limit)
graph = [[] for _ in range(N+1)] # 1-indexed
for u, v, a, b in UVAB:
    graph[u].append((v, a, b))
    graph[v].append((u, a, b))

def dijkstra(start):
    # 時間、銀貨の枚数、現在地をqueへ
    INF = 10 ** 15
    dist = [[INF for _ in range(limit+1)] for _ in range(N+1)]
    dist[1][S] = 0
    que = [(0, S, 1)]
    while que:
        time, silver, prev = heappop(que)
        if dist[prev][silver] < time:
            continue
        for next, a, b in graph[prev]:
            t = time + b
            si = silver - a
            if si < 0:
                continue
            if dist[next][si] > t:
                dist[next][si] = t
                heappush(que, (t, si, next))
        c, d = CD[prev-1]
        si = min(limit, silver+c)
        while dist[prev][si] > time + d:
            dist[prev][si] = time + d
            heappush(que, (time+d, si, prev))
            si += c; si = min(limit, si)
            time += d
            
    return dist

dist = dijkstra(1)
for i in range(2, N+1):
    d = dist[i]
    answer = min(d)
    print(answer)

# 52
a, b = map(int, input().split())
for n in range(1, 4):
  if a*b*c % 2 == 1:
    print('Yes')
    break
  else:
    if n == 3:
      print('No')

### FIXED CODE ###

a, b = map(int, input().split())
for c in range(1, 4):
  if a*b*c % 2 == 1:
    print('Yes')
    break
  else:
    if c == 3:
      print('No')
a,b,k = map(int,input().split())
m = []
for i in range(min(a,b)+1,1,-1):
    if a%i == 0 and b%i == 0:
        m.append(i)
print(m)
print(m[k-1])

### FIXED CODE ###

A, B, K = map(int, input().split())
 
cand = []
for i in range(100,0,-1):
  if A%i == 0 and B%i == 0:
    cand += [i]
    
    
print(cand[K-1])
N, M = map( int, input().split())
A = list( map( int, input().split()))
Needs = [0,2,5,5,4,5,6,3,7,6]
A.sort(reverse = True)
V = [0]*N
Check = []
for a in A:
    if V[Needs[a]] == 0:
        Check.append(Needs[a])
        V[Needs[a]] = a
Check.sort()
dp = [-100]*(N+1)
dp[0] = 0

for x in Check:
    dp[x] = 1
for i in range(1,N):
    t = dp[i]
    if t == 0:
        continue
    for x in Check:
        if x + i <= N:
            if dp[x+i] < t + 1:
                dp[x+i] = t+1
ans = ""
t = N
W = [0]*10
while t > 0:
    for x in Check:
        if dp[t-x]+1 == dp[t]:
            W[V[x]] += 1
            t -= x
            break
for i in range(9,0,-1):
    ans += str(i)*W[i]
print(ans)


### FIXED CODE ###

N, M = map( int, input().split())
A = list( map( int, input().split()))
Needs = [0,2,5,5,4,5,6,3,7,6]
A.sort(reverse = True)
V = [0]*10
Check = []
for a in A:
    if V[Needs[a]] == 0:
        Check.append(Needs[a])
        V[Needs[a]] = a
Check.sort()
dp = [-100000]*(N+1)
dp[0] = 0

for x in Check:
    if x <= N:
        dp[x] = 1
for i in range(1,N):
    t = dp[i]
    for x in Check:
        if x + i <= N:
            if dp[x+i] < t + 1:
                dp[x+i] = t+1
ans = ""
t = N
W = [0]*10
while t > 0:
    for a in A:
        x = Needs[a]
        if t-x>=0:
            if dp[t-x]+1 == dp[t]:
                W[V[x]] += 1
                t -= x
                break
for i in range(9,0,-1):
    ans += str(i)*W[i]
print(ans)
n,k=int(input())
A=list(map(int,input().split()))

right=10**9
left=1

while right-left>1 :
    mid=(left+right)//2
    count=0
    for a in A :
        count+=a//mid
        if a%mid==0 :
            count-=1
    if count<=k :
        right=mid
    else :
        left=mid

print(right)

### FIXED CODE ###

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

right=10**9
left=0

while right-left>1 :
    mid=(left+right)//2
    count=0
    for a in A :
        count+=a//mid
        if a%mid==0 :
            count-=1
    if count<=k :
        right=mid
    else :
        left=mid

print(right)
l, r = map(int, input().split())
a = []
if r - l >= 2019:
    print(0)
else:
    for i in range(r - l + 1):
        a.append((l + i) % 2019)
# print(a)
a.sort()
print(a[0] * a[1])


### FIXED CODE ###

l, r = map(int, input().split())
a = []

data = 2019

if r - l + 1 >= 2019:
    print(0)
    exit()

else:
    for i in range(l, r + 1):
        for j in range(i+1, r + 1):
            data = min(data, i * j % 2019)

print(data)
h,n = map(int, input().split())
magics = [tuple(map(int, input().split())) for _ in range(n)]
dp = [0]*(h+1)
for i in range(1, h+1):
  dp[i] = min(dp[i-a]+b for a,b in magics)
print(dp[h])

### FIXED CODE ###

h,n = map(int, input().split())
magics = [tuple(map(int, input().split())) for _ in range(n)]
max_a = sorted(magics, key=lambda x: x[0], reverse=True)[0][0]
dp = [0]*(h+max_a)
for i in range(1, h+max_a):
  dp[i] = min(dp[i-a]+b for a,b in magics)
print(min(dp[h:]))
n, x = map(int, input().split())
li = list(map(int, input().split()))
a = 0
i = 0
while a < x and i < n+1:
  a += li[i]
  i += 1
if a == x:
  i += 1
print(i)
  

### FIXED CODE ###

n, x = map(int, input().split())
li = list(map(int, input().split()))
li.append(0)
a = 0
i = 0
while a <= x and i < n+1:
  a += li[i]
  i += 1
print(i)
n = int(input())
a = list(map(int, input().split()))
ans = 1 
if 0 in a:
    print(0)
    return 0
for i in a:
    ans *= i
    if ans > 10**18:
        ans = -1
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
ans = 1 
if 0 in a:
    print(0)
    sys.exit(0)
for i in a:
    ans *= i
    if ans > 10**18:
        print(-1)
        sys.exit(0)
print(ans)
a = [list(map(int,input().split())) for _ in range(3)]
n = int(input())
b = [int(input()) for _ in range(n)]
ans  = 'No'
for i in range(3):
  for j in range(3):
    for k in b:
      if a[i][j] == k:
        a[i][j] = 0
for i in range(3):
  if a[i][0] + a[i][1] + a[i][2] == 0:
    ans = 'Yes'
  if a[0][i] + a[1][i] + a[2][i] == 0:
    ans = 'Yes'
if A[0][0]+A[1][1]+A[2][2]==0:
  ans = "Yes"
if A[0][2]+A[1][1]+A[2][0]==0:
  ans = "Yes"
print(ans)

### FIXED CODE ###

a = [list(map(int,input().split())) for _ in range(3)]
n = int(input())
b = [int(input()) for _ in range(n)]
ans  = [[False]*3 for _ in range(3)]
result = 'No'
for i in range(3):
  for j in range(3):
    for k in b:
      if a[i][j] == k:
        ans[i][j] = True 
for i in ans:
    if all(i):
      result = 'Yes'
for i in range(3):
  cnt = 0
  for j in range(3):
    if ans[j][i]:
      cnt += 1
  if cnt == 3:
    result = 'Yes'
    break
if ans[0][0] and ans[1][1] and ans[2][2]:
  result = "Yes"
if ans[0][2] and ans[1][1] and ans[2][0]:
  result = "Yes"
print(result)
def main():
    import sys
    input = sys.stdin.readline

    from fractions import gcd

    def lcd(x, y):
        g = gcd(x, y)
        return x * y // g

    n = int(input())
    a = tuple(map(int, input().split()))
    mod = 10 ** 9 + 7

    a.sort(reverse=True)
    l = 1
    for e in a:
        l = lcd(l, e)

    ans = 0
    for e in a:
        ans += (l // e) % mod
        ans %= mod

    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

from fractions import gcd


def lcm(a, b):
    return a * b // gcd(a, b)


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

l = 1
for e in a:
    l = lcm(l, e)

l %= mod

ans = 0
for e in a:
    ans += l * pow(e, mod - 2, mod)
    ans %= mod

print(ans)
import sys
N,M=map(int, input().split())
a=[]
b=[]
c=[]
for m in range (0,M):
  A,B,C=map(int, input().split() )
  a+=[A]
  b+=[B]
  c+=[C]
V=[0]+[-10**12]*(N-1)# iに到達するときの最大得点
 
for n in range(N-1):
  for m in range(M):
    u=a[m]
    v=b[m]
    if V[b[m]-1]<V[a[m]-1]+c[m]:#共に有限の時はやる
      V[b[m]-1]=V[a[m]-1]+c[m]
 
moji2=[0]*N
for n in range(N):
  for m in range(M):
    u=a[m]
    v=b[m]
    if V[b[m]-1]<V[a[m]-1]+c[m]:#共に有限の時はやる
        V[b[m]-1]=V[a[m]-1]+c[m]
        moji2[b[m]-1]=1
      if moji2[N-1]:
        print("inf")
        sys.exit()
print(V[N-1])

### FIXED CODE ###

import sys
N,M=map(int, input().split())
a=[]
b=[]
c=[]
for m in range (0,M):
  A,B,C=map(int, input().split() )
  a+=[A]
  b+=[B]
  c+=[C]
V=[0]+[-10**12]*(N-1)# iに到達するときの最大得点
 
for n in range(N-1):
  for m in range(M):
    u=a[m]
    v=b[m]
    if V[b[m]-1]<V[a[m]-1]+c[m]:#共に有限の時はやる
      V[b[m]-1]=V[a[m]-1]+c[m]
 
moji2=[0]*N
for n in range(N):
  for m in range(M):
    u=a[m]
    v=b[m]
    if V[b[m]-1]<V[a[m]-1]+c[m]:#共に有限の時はやる
      V[b[m]-1]=V[a[m]-1]+c[m]
      moji2[b[m]-1]=1
      if moji2[N-1]:
        print("inf")
        sys.exit()
print(V[N-1])
s = input().split()

n = 0
for symbol in s:
    if symbol == '+':
        n += 1
    else
        n -= 1
print(n)

### FIXED CODE ###

s = input()

n = 0
for symbol in s:
    if symbol == '+':
        n += 1
    else:
        n -= 1
print(n)
l,r = input().split()
N = 2019
  
ans = (l * (l + 1)) % N;
count = 0;
for i in range(l,r-1):
  if(count >= (N - 1)) break
  for j in range(l+1,r):
    if(count >= (N - 1)) break
    if(ans > (i * j) % N) ans = (i * j) % N
    count++;
    
printf("%lu\n",ans);
return 0

### FIXED CODE ###

l,r = input().split()
l = int(l)
r = int(r)
N = int(2019)
  
ans = N
count = 0
right = min(l + N, r)
for i in range(l,right):
  for j in range(i+1,right+1):
    ans = min(ans, (i * j) % N)
    
print(ans)
import sys

N, M = map(int, input().split())

S = []
C = []
for m in range(M):
  s, c = map(int, input().split())
  S.append(s)
  C.append(c)

for i in range(10**N):
  tes = str(i)
  flag = True
  if len(tes) < N:
    flag = False
  for s, c in zip(S, C):
    if tes[s-1] != str(c):
      flag = False
  if flag:
    print(tes)
    sys.exit()


print(-1)


### FIXED CODE ###

import sys
N, M = map(int, input().split())

A = [-1] * N

for i in range(M):
  s, c = map(int, input().split())
  if A[s-1] != c and A[s-1] != -1:
    print(-1)
    sys.exit()
  else:
    A[s-1] = c
  
if N >= 2 and A[0] == 0:
  print(-1)
  sys.exit()

res = 0

for i in range(N):
  if A[i] == -1:
    if i == 0 and N >= 2:
      A[i] = 1
    else:
      A[i] = 0
  res += A[i] * 10 ** (N-i-1)

print(res)
N,M = map(int,input().split())
A = [int(a) for a in input().split()]
BC = [[int(x) for x in input().split()] for _ in range(M)]

A.sort(reverse=True)
BC.sort(key=lambda x:x[1], reverse=True)

def bysectsearch(List,num,Left):
    Right = len(List)-1
    while True:
        Midle = (Left+Right)//2
        if List[Left]<=num:
            return Left
        if List[Right]>=num:
            return Right+1
        if Right-Left<=1:
            return Right
        if List[Midle]==num:
            return Midle
        if List[Midle]>num:
            Left = Midle
            continue
        if List[Midle]<num:
            Right = Midle
            continue

Left = 0
for B,C in BC:
    insert_point = bysectsearch(A,C,Left)
    if insert_point == N:
        break
    A = A[:insert_point]+[C]*B+A[insert_point:]
    A = A[:N]
    Left = insert_point + B
print(sum(A))


### FIXED CODE ###

N,M = map(int,input().split())
A = [int(a) for a in input().split()]
BC = [[int(x) for x in input().split()] for _ in range(M)]

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

count = 0
Added_list = []
for i in range(M):
    B,C = BC[i]
    Added_list += [C]*B
    count += B
    if count>N:
        Added_list = Added_list[:N]
        break

A += Added_list
A.sort(reverse=True)
print(sum(A[:N]))
takahashi, aoki, kaisu = [int(x) for x in input().split()]
taka_amari = takahashi - kaisu
if taka_amari<0:
    ao_amari = aoki+taka_amari

if taka_amari<0:
    taka_amari = 0
if ao_amari<0:
    ao_amari = 0
print(str(taka_amari) + " " + str(ao_amari))

### FIXED CODE ###

takahashi, aoki, kaisu = [int(x) for x in input().split()]
taka_amari = takahashi - kaisu
ao_amari = aoki
if taka_amari<0:
    ao_amari = aoki+taka_amari
 
if taka_amari<0:
    taka_amari = 0
if ao_amari<0:
    ao_amari = 0
print(str(taka_amari) + " " + str(ao_amari))
x,y=map(int,input().split())
if 2x<=y<=4x and y%2==0:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

x,y=map(int,input().split())
if 2*x<=y<=4*x and y%2==0:
  print("Yes")
else:
  print("No")
while True:
	students,places = map(int,raw_input().split())
	if students=0 and places~0:
		break
	res = dict(zip(range(places),[0]*places))
	for i in range(students):
		points = map(int,raw_input().split())
		for j in range(places):
			res[j] += points[j]
	for k,v in sorted(res.items(),key=lambda x:x[1], reverse=True):
		print k,

### FIXED CODE ###

while True:
	students,places = map(int,raw_input().split())
	if students == 0 and places == 0:
		break
	res = dict(zip(range(places),[0]*places))
	for i in range(students):
		points = map(int,raw_input().split())
		for j in range(places):
			res[j] += points[j]
	for k,v in sorted(res.items(),key=lambda x:x[1], reverse=True):
		print k+1,
	print
n,l = map(int,input().ssplit())
s = sorted([int(input()) for i in range(n)])
print(*s,sep="")

### FIXED CODE ###

n,l = map(int,input().split())
s = sorted([input() for i in range(n)])
print(*s,sep='')
a=input()
i=0
while i<a:
    if a[i]='?':
        print(end='D')

    else:
        print(end=str(a[i]))
    i=i+1

### FIXED CODE ###

a=input()
i=0
while i<len(a):
    if a[i]=='?':
        print(end='D')

    else:
        print(end=str(a[i]))
    i=i+1
s = input()

n = int(input())

alphabet = ["A","B","C","D","E","F","G","H","I","J","K","L","M","M","O","P","Q","R","S","T","U","V","W","X","Y","Z"]

ans = ""
for i in range(len(s)):
    num = ( alphabet.index(s[i]) + n ) % 26
    ans += alphabet[num]
    
print(ans)

### FIXED CODE ###

n = int(input())
 
s = input()
 
alphabet = ["A","B","C","D","E","F","G","H","I","J","K","L","M","N","O","P","Q","R","S","T","U","V","W","X","Y","Z"]
 
ans = ""
for i in range(len(s)):
    num = (alphabet.index(s[i]) + n) % len(alphabet)
    ans += alphabet[num]
    
print(ans)
N,K=(int(x) for x in input().split())
lists=[0]*N
while 1:
    tmp=int(input())
    if not tmp:
        break
    have_count=(int(x) for x in input().split())
    for i in have_count:
        lists[i-1]=1
print(lists.count(0))

### FIXED CODE ###

N,K=(int(x) for x in input().split())
lists=[0]*N
while 1:
    try:
        tmp=int(input())
    except :
        break
    have_count=(int(x) for x in input().split())
    for i in have_count:
        lists[i-1]=1
print(lists.count(0))
import math
n,k=map(int, input().split()) 
lst=list()

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

for i in range(1, k+1):
    lst.append(combinations_count(n-k+1, i) * combinations_count(k-i+(i-1), i-1))
        
for i in range(k):
    print(lst[i]%(10**9+7))

### FIXED CODE ###

import math
n,k=map(int,input().split()) 

def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

mod_num = 10 ** 9 + 7
for i in range(1, k+1):
    if i > n - k + 1:
        print(0)
    else:
        print(comb(n-k+1, i) * comb(k-i+(i-1), i-1) % mod_num)
# -*- coding: utf-8 -*-
import math
import sys
import itertools
import numpy as np
import functools
import collections
mo = 1000000007
INF = 10**100
r = range

class infix(object):
    def __init__(self, function):
        self.function = function

    def __ror__(self, other):
        self.left = other
        return self

    def __or__(self, other):
        return self.function(self.left, other)

    def __call__(self, value1, value2):
        return self.function(value1, value2)

@infix
def c(f_t_u, f_u_r): return lambda t: f_u_r(f_t_u(t))

class _Ap(object):
    def __rlshift__(self, other):
        self.value = other
        return self

    def __rshift__(self, other):
        return other(self.value)
Ap = _Ap()
A = Ap

#d = {1:2, 3:5, 6:10, 1000043:3814}
#zip(d.keys(), d.values())<<ap>>(list |c| sorted |c| reversed |c| list |c| print)

n=input()<<A>>int
ret = 1
for i in range(n): a=int(input()); ret = ret * a // math.gcd(ret, a)
print(ret);


### FIXED CODE ###

# -*- coding: utf-8 -*-
import math
import sys
import itertools
import numpy as np
import functools
import collections
mo = 1000000007
INF = 10**100
r = range

class infix(object):
    def __init__(self, function):
        self.function = function

    def __ror__(self, other):
        self.left = other
        return self

    def __or__(self, other):
        return self.function(self.left, other)

    def __call__(self, value1, value2):
        return self.function(value1, value2)

@infix
def c(f_t_u, f_u_r): return lambda t: f_u_r(f_t_u(t))

class _Ap(object):
    def __rlshift__(self, other):
        self.value = other
        return self

    def __rshift__(self, other):
        return other(self.value)
Ap = _Ap()
A = Ap

#d = {1:2, 3:5, 6:10, 1000043:3814}
#zip(d.keys(), d.values())<<ap>>(list |c| sorted |c| reversed |c| list |c| print)

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

n=input()<<A>>int
ret = 1
for i in range(n): a=int(input()); ret = ret * a // gcd(ret, a)
print(ret);
n = int(input())

used = []
ans = "Yes"

for i in range(n):
    if i == 0:
        t = str(input())
        
        past = t
    else:
        t = str(input())
        for j in used:
            if j == t:
                ans = "No"
    
    if past[-1] != t[1]:
        ans = "No"
    used.append(t)
    past = t

print(ans)

    
    


### FIXED CODE ###


s = int(input())
last = str(input())
wordlist = [last]
ans = "Yes"

for i in range(s-1):
    word = str(input())

    if last[-1] != word[0]:
        ans = "No"
        break
    
    elif word in wordlist:
        ans = "No"
        break

    last = word
    wordlist.append(word)

print(ans)
import sys
N, M = map(int, input().split())

a_list = [0] * M

for m in range(M):
    a_list[m] = int(input())

for m in range(M - 1):
    if a_list[m] + 1 == a_list[m + 1]:
        print(0)
        sys.exit()
    else:
        continue

range_list = [i for i in range(1, N + 1)]
new_list = [0] * (M + 1)

a = 0
if a_list[0] == 1:
    new_list[0] = []
else:
    new_list[0] = [0] + range_list[0: a_list[0] - 1]
new_list[M] = range_list[a_list[M - 1]:]

if M - 1 >= 1:
    for m in range(1, M):
        new_list[m] = range_list[a_list[m - 1]: a_list[m] - 1]

MOD = 1000000007

def fib(n):
    dp_list = [0] * n
    dp_list[0] = 1
    dp_list[1] = 2
    
    for i in range(2, n):
        dp_list[i] = dp_list[i - 1] + dp_list[i - 2]
    return dp_list[n - 1]

count = 1
for item in new_list:
    if not item:
        continue
    else:
        count *= (fib(len(item) - 1) & MOD)
        count %= MOD
print(count)

### FIXED CODE ###

import sys
N, M = map(int, input().split())

MOD = 1000000007

def fib(n):
    dp_list = [0] * n
    dp_list[0] = 1
    if n == 1:
        return 1
    dp_list[1] = 2
    
    for i in range(2, n):
        dp_list[i] = dp_list[i - 1] + dp_list[i - 2]
    return dp_list[n - 1]

if M == 0:
    print(fib(N) % MOD)
    sys.exit()

a_list = [0] * M

for m in range(M):
    a_list[m] = int(input())

for m in range(M - 1):
    if a_list[m] + 1 == a_list[m + 1]:
        print(0)
        sys.exit()
    else:
        continue

range_list = [i for i in range(1, N + 1)]
new_list = [0] * (M + 1)


new_list[0] = [0] + range_list[0: a_list[0] - 1]
new_list[M] = range_list[a_list[M - 1]:]

if M - 1 >= 1:
    for m in range(1, M):
        new_list[m] = range_list[a_list[m - 1]: a_list[m] - 1]

count = 1
for item in new_list:
    if not item or len(item) == 1:
        continue
    else:
        count *= (fib(len(item) - 1) % MOD)
        count %= MOD
        #print(count)
print(count)
x = int(input())

a = 100
i = 0

while a < 18:
  print("a="+str(a))
  i+ = a
  a+ = 1

print(x/a)
  



### FIXED CODE ###

x = int(input())

a = 100
i = 0

while a < x:
  i += 1
  a += a // 100
  
  
print(i)
import sys

# import bisect
# from collections import Counter, deque, defaultdict
# import copy
# from heapq import heappush, heappop, heapify
# from fractions import gcd
# import itertools
# from operator import attrgetter, itemgetter

# import math

from numba import jit

# from scipy import
# import numpy as np
# import networkx as nx

# import matplotlib.pyplot as plt

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n, k = list(map(int, readline().split()))

    b = k
    r = n - k

    @jit(nopython=True)
    def comb():
        com = [[0] * 2005 for _ in range(2005)]
        com[0][0] = 1
        for i in range(1, 2005):
            com[i][0] = 1
            for j in range(1, 2005):
                com[i][j] = (com[i - 1][j - 1] + com[i - 1][j]) % MOD
        return com

    com = comb()

    for i in range(1, k + 1):
        res = com[r + 1][i] * com[b - 1][i - 1]
        res %= MOD
        print(res)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

# import bisect
# from collections import Counter, deque, defaultdict
# import copy
# from heapq import heappush, heappop, heapify
# from fractions import gcd
# import itertools
# from operator import attrgetter, itemgetter

# import math

# from numba import jit

# from scipy import
# import numpy as np
# import networkx as nx

# import matplotlib.pyplot as plt

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n, k = list(map(int, readline().split()))

    b = k
    r = n - k

    def comb():
        com = [[0] * 2005 for _ in range(2005)]
        com[0][0] = 1
        for i in range(1, 2005):
            com[i][0] = 1
            for j in range(1, 2005):
                com[i][j] = (com[i - 1][j - 1] + com[i - 1][j]) % MOD
        return com

    com = comb()

    for i in range(1, k + 1):
        res = com[r + 1][i] * com[b - 1][i - 1]
        res %= MOD
        print(res)


if __name__ == '__main__':
    main()