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

import sys
from collections import deque

def main(*args, **kwargs):
    # Initialize data
    H, W = map(int, sys.stdin.readline().split())
    total_cells = H * W
    existing_black_cells = 0

    grid = []
    for i in range(H):
        line = sys.stdin.readline()
        existing_black_cells += line.count('#')
        grid.append(line)

    # Initialize Search
    queue = deque()
    queue.append((0, 0))  # start point
    visited = set()
    movement = 0

    while len(queue) > 0:
        movement += 1
        for i in range(len(queue)):  # Process same level
            coodinate = queue.popleft()
            visited.add(coodinate)
            y = coodinate[0]
            x = coodinate[1]

            # Terminate condition
            if y == H - 1 and x == W - 1:
                print(total_cells - movement - existing_black_cells)
                return

            for dx, dy in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
                X = x + dx
                Y = y + dy
                adjacent = (Y, X)
                if 0 <= X < W and 0 <= Y < H and grid[Y][X] == '.' and adjacent not in visited:
                    queue.append(adjacent)
    print(-1)
    return
main()

### FIXED CODE ###

import sys
from collections import deque
    
def main(*args, **kwargs):
    # Initialize data
    H, W = map(int, sys.stdin.readline().split())
    total_cells = H * W
    existing_black_cells = 0
 
    grid = []
    for i in range(H):
        line = sys.stdin.readline()
        existing_black_cells += line.count('#')
        grid.append(line)
 
    # Initialize Search
    queue = deque()
    queue.append((0, 0))  # start point
    visited = set()
    visited.add((0, 0))
    movement = 0
 
    while len(queue) > 0:
        movement += 1
        for i in range(len(queue)):  # Process same level
            coodinate = queue.popleft()
            y = coodinate[0]
            x = coodinate[1]
 
            # Terminate condition
            if y == H - 1 and x == W - 1:
                print(total_cells - movement - existing_black_cells)
                return
 
            for dx, dy in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
                X = x + dx
                Y = y + dy
                adjacent = (Y, X)
                if 0 <= X < W and 0 <= Y < H and grid[Y][X] == '.' and adjacent not in visited:
                    queue.append(adjacent)
                    visited.add(adjacent)
    print(-1)
    return
main()
### BUGGY CODE ###

def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    to = [[None]*n for _ in range(60)]
    double = 1
    i = 0
    to[0] = a[:]
    for i in range(1, 60):
        for j in range(n):
            to[i][j] = to[i-1][to[i-1][j]-1]
    num = 2**59
    p = 1
    for i in range(59, -1, -1):
        if k >= num:
            k -= num
            p = to[i][p-1]
        num //= 2
    print(p)
        
    

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    if a[0] == 1:
        print(1)
        exit(0)
    if a[0] == a[a[0]-1]:
        print(a[0])
        exit(0)
    pos = a[0]
    num = 1
    nums = set([1])
    while pos not in nums:
        nums.add(pos)
        num += 1
        pos = a[pos-1]
    lastnum = pos
    prefix = 0
    pos = 1
    while pos != lastnum:
        prefix += 1
        pos = a[pos-1]
    num -= prefix
    if k > prefix:
        k = (k-prefix)%num+prefix
    pos = 1
    for _ in range(k):
       pos = a[pos-1]
    print(pos)

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

from bisect import bisect_left, bisect_right
import math
import sys
input = sys.stdin.readline


def main():
    N = int(input())
    X = list(map(int, input().split()))
    L = int(input())
    ln = int(math.log(N, 2))
    dpl = [[0] * N for _ in range(ln+1)]
    dpr = [[0] * N for _ in range(ln+1)]
    for i in range(N):
        x = X[i]
        l = bisect_left(X, x - L)
        r = bisect_right(X, x + L) - 1
        dpl[0][i] = l
        dpr[0][i] = r
    for k in range(1, ln+1):
        for i in range(N):
            dpl[k][i] = dpl[k-1][dpl[k-1][i]]
            dpr[k][i] = dpr[k-1][dpr[k-1][i]]
    Q = int(input())
    for _ in range(Q):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        ans = 0
        if a < b:
            for k in range(ln+1)[::-1]:
                while dpr[k][a] <= b:
                    a = dpr[k][a]
                    ans += 2**k
            if a < b:
                ans += 1
        else:
            # a > b
            for k in range(ln+1)[::-1]:
                while dpl[k][a] >= b:
                    a = dpl[k][a]
                    ans += 2**k
            if a > b:
                ans += 1
        print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

from bisect import bisect_left, bisect_right
import math
import sys
input = sys.stdin.readline


def main():
    N = int(input())
    X = list(map(int, input().split()))
    L = int(input())
    ln = int(math.log(N, 2))
    dpl = [[0] * N for _ in range(ln+1)]
    dpr = [[0] * N for _ in range(ln+1)]
    l = 0
    r = 0
    for i in range(N):
        x = X[i]
        while X[l] + L < x:
            l += 1
        while r < N-1 and x + L >= X[r+1]:
            r += 1
        dpl[0][i] = l
        dpr[0][i] = r
    for k in range(1, ln+1):
        for i in range(N):
            dpl[k][i] = dpl[k-1][dpl[k-1][i]]
            dpr[k][i] = dpr[k-1][dpr[k-1][i]]
    Q = int(input())
    for _ in range(Q):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        ans = 0
        if a < b:
            for k in range(ln+1)[::-1]:
                if dpr[k][a] < b:
                    a = dpr[k][a]
                    ans += 2**k
            if a < b:
                ans += 1
        else:
            # a > b
            for k in range(ln+1)[::-1]:
                if dpl[k][a] > b:
                    a = dpl[k][a]
                    ans += 2**k
            if a > b:
                ans += 1
        print(ans)


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

# coding: utf-8
import sys
from collections import defaultdict

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

S = sr()
dic = defaultdict(int)
dic[0] = 1
remain = 0
answer = 0
for i in range(len(S)-1, -1, -1):
    remain += 10 ** (len(S)-1-i) * int(S[i])
    remain %= 2019
    answer += dic[remain]
    dic[remain] += 1

print(answer)


### FIXED CODE ###

# coding: utf-8
import sys

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

S = sr()
mod_cnt = [0] * 2019
mod_cnt[0] = 1
power = 1
remain = 0
answer = 0
for i in range(len(S)-1, -1, -1):
    remain += int(S[i]) * power
    remain %= 2019
    power *= 10; power %= 2019
    answer += mod_cnt[remain]
    mod_cnt[remain] += 1

print(answer)
### BUGGY CODE ###

def check(startA, startB, S, T, a, b):
  pat1 = float("inf")
  if startA >= 0:
    pat1 = x - S[startA]
    if startB >= 0 and S[startA] > T[startB]:
      if startB != b - 1:
        pat1 += min(S[startA] - T[startB], T[startB + 1] - S[startA])
      else:
        pat1 += S[startA] - T[startB]
    elif startB == -1 and S[startA] < T[0]:
      pat1 += T[0] - S[startA]
  pat2 = float("inf")
  if startA != a - 1:
    pat2 = S[startA + 1] - x
    if startB != b - 1 and S[startA + 1] < T[startB + 1]:
      if startB != -1:
        pat2 += min(T[startB + 1] - S[startA + 1], S[startA + 1] - T[startB])
      else:
        pat2 += T[startB + 1] - S[startA + 1]
    elif startB == b - 1 and S[startA + 1] > T[b - 1]:
      pat2 +=  S[startA + 1] - T[b - 1]
  return min(pat1, pat2)
  
a, b, q = map(int, input().split())
S = [int(input()) for _ in range(a)]
T = [int(input()) for _ in range(b)]
X = [int(input()) for _ in range(q)]

for x in X:
  startA = -1
  for i in range(a):
    if x - S[i] > 0:
      startA = i
  startB = -1
  for i in range(b):
    if x - T[i] > 0:
      startB = i
  
  print(min(check(startA, startB, S, T, a, b), check(startB, startA, T, S, b, a)))

### FIXED CODE ###

def check(startA, startB, S, T, a, b):
  pat1 = float("inf")
  if startA >= 0:
    pat1 = x - S[startA]
    if startB >= 0 and S[startA] > T[startB]:
      if startB != b - 1:
        pat1 += min(S[startA] - T[startB], T[startB + 1] - S[startA])
      else:
        pat1 += S[startA] - T[startB]
    elif startB == -1 and S[startA] < T[0]:
      pat1 += T[0] - S[startA]
  pat2 = float("inf")
  if startA != a - 1:
    pat2 = S[startA + 1] - x
    if startB != b - 1 and S[startA + 1] < T[startB + 1]:
      if startB != -1:
        pat2 += min(T[startB + 1] - S[startA + 1], S[startA + 1] - T[startB])
      else:
        pat2 += T[startB + 1] - S[startA + 1]
    elif startB == b - 1 and S[startA + 1] > T[b - 1]:
      pat2 +=  S[startA + 1] - T[b - 1]
  return min(pat1, pat2)
  
a, b, q = map(int, input().split())
S = [int(input()) for _ in range(a)]
T = [int(input()) for _ in range(b)]
X = [int(input()) for _ in range(q)]
import bisect
for x in X:
  startA = bisect.bisect_left(S,x) - 1
  startB = bisect.bisect_left(T,x) - 1
  
  print(min(check(startA, startB, S, T, a, b), check(startB, startA, T, S, b, a)))
### BUGGY CODE ###

import sys
from collections import defaultdict as dd
input = sys.stdin.readline
N, M = map(int, input().split())
a = [0] + list(map(int, input().split()))
edg = []
for i in range(1, M + 1):
  u, v, c = map(int, input().split())
  edg.append((u, v, c, i))

def check(x):
  e = dd(list)
  for u, v, c, i in edg:
    if c > x: continue
    e[u].append((v, c, i))
    e[v].append((u, c, i))

  vis = [0] * (N + 1)
  for i in range(1, N + 1):
    if vis[i]: continue
    s = [i]
    vs = 0
    es = 0
    evis = [0] * (M + 1)
    while len(s):
      p = s.pop()
      if vis[p]: continue
      vis[p] = 1
      vs += a[p]
      for q, c, k in e[p]:
        if evis[k]: continue
        es = max(es, c)
        evis[k] = 1
        s.append(q)
    if vs < es: return False
  return True

ok = 0
ng = sum(a) + 1
while ng - ok > 1:
  m = (ok + ng) // 2
  if check(m): ok = m
  else: ng = m

res = 0
for _, _, c, _ in edg: res += c > ok
print(res)

### FIXED CODE ###

import sys
from collections import Counter
input = sys.stdin.readline
N, M = map(int, input().split())
a = list(map(int, input().split()))
e = []
ee = [[] for _ in range(N + 1)]
for _ in range(M):
  u, v, c = map(int, input().split())
  e.append((c, u, v))
  ee[u].append((v, c))
  ee[v].append((u, c))
e.sort()

table = [0] + a[: ]

class UnionFind():
  def __init__(self, n):
    self.n = n
    self.root = [-1] * (n + 1)
    self.rnk = [0] * (n + 1)

  def Find_Root(self, x):
    if self.root[x] < 0:
      return x
    else:
      self.root[x] = self.Find_Root(self.root[x])
      return self.root[x]

  def Unite(self, x, y):
    x = self.Find_Root(x)
    y = self.Find_Root(y)
    if x == y:
      return 
    elif self.rnk[x] > self.rnk[y]:
      self.root[x] += self.root[y]
      self.root[y] = x
    else:
      self.root[y] += self.root[x]
      self.root[x] = y
      if self.rnk[x] == self.rnk[y]:
        self.rnk[y] += 1

  def isSameGroup(self, x, y):
    return self.Find_Root(x) == self.Find_Root(y)

  def Count(self, x):
    return -self.root[self.Find_Root(x)]

uf = UnionFind(N)
edges = []
etable = [0] * (N + 1)
for i in range(M):
  c, u, v = e[i]
  if uf.isSameGroup(u, v):
    rt = uf.Find_Root(u)
    etable[rt] = max(etable[rt], c)
    if table[rt] >= etable[rt]: edges.append(i)

  else:
    ur = uf.Find_Root(u)
    vr = uf.Find_Root(v)
    uf.Unite(u, v)
    rt = uf.Find_Root(u)
    cmx = max(etable[ur], etable[vr], c)
    etable[rt] = cmx
    if table[ur] + table[vr] >= cmx: edges.append(i)

    table[rt] = table[ur] + table[vr]
edges.reverse()
vis = [0] * (N + 1)
evis = Counter()
res = M
#print(edges)
for i in edges:
  mx, s, _ = e[i]
  if vis[s]: continue
  sta = [s]
  vis[s] = 1
  while len(sta):
    x = sta.pop()
    for y, c in ee[x]:
      if c > mx: continue
      if evis[(min(x, y), max(x, y))]: continue
      evis[(min(x, y), max(x, y))] = 1
      res -= 1
      if vis[y]: continue
      sta.append(y)
      vis[y] = 1
  #print(vis, res, e[i])
print(res)
### BUGGY CODE ###

n,m= map(int,input().split())
for i in range(m):
    a,b = map(int,input().split())
    if i == 0:
        l = [a+j for j in range(b-a+1)]
    l = list(set([a+j for j in range(b-a+1)]) & set(l))
print(len(set(l)))

### FIXED CODE ###

n,m = map(int, input().split())
left = 0
right = 10**5
for _ in range(m):
    l,r = map(int,input().split())
    left = max(left, l)
    right = min(right,r)
print(max(0,right-left+1))
### BUGGY CODE ###

# dp[i][w_sum]: i-1番目までの品物で重さがw_sumを超えないように選んだときの、価値の総和の最大値

N, W = map(int, input().split())
items = [tuple(map(int, input().split())) for i in range(N)]

dp = [[0 for w_sum in range(W+100)] for i in range(N+100)]

for i in range(N):
    for w_sum in range(W+1):

        # i-1番目の品物を選ぶ場合
        # 重量的に入れられるなら入れてみる
        if w_sum-items[i][0] >= 0:
            dp[i+1][w_sum] = max(dp[i+1][w_sum],
                                 dp[i][w_sum-items[i][0]]+items[i][1])

        # i-1番目の品物を選ばない場合
        dp[i+1][w_sum] = max(dp[i+1][w_sum], dp[i][w_sum])

print(dp[N][W])


### FIXED CODE ###

# dp[i][w_sum]: i番目までの品物で重さがw_sumを超えないように選んだときの、価値の総和の最大値

N,W=map(int,input().split())
items=[tuple(map(int,input().split())) for i in range(N)]
items.insert(0, (0,0))

dp=[[0 for _ in range(W+1)] for _ in range(N+1)]

for i in range(1,N+1):
    for j in range(W+1):
        # take item
        if j-items[i][0]>=0:
            dp[i][j]=dp[i-1][j-items[i][0]]+items[i][1]
        
        dp[i][j]=max(dp[i][j],dp[i-1][j])

print(dp[N][W])
### BUGGY CODE ###

#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin, maxint


def main():
    num = int(stdin.readline())

    L = []
    for _ in xrange(num):
        it = iter(int(s) for s in stdin.readline().split()[1:])
        L.append([(next(it), next(it)) for _ in xrange(next(it))])

    weight = [maxint] * num
    weight[0] = 0
    V = set(xrange(1, num))
    index = 0

    while V:
        for v, cost in L[index]:
            if v not in V:
                continue
            weight[v] = min(weight[v], cost + weight[index])

        index = min(V, key=lambda i: weight[i])
        V.remove(index)

    for i, d in enumerate(weight):
        print(i, d)


main()

### FIXED CODE ###

#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin, maxsize


def main():
    num = int(stdin.readline())

    edges = []
    for _ in range(num):
        ns = [int(s) for s in stdin.readline().split()]
        for i in range(ns[1]):
            edges.append((ns[0], ns[2*i+2], ns[2*i+3]))

    dis = [maxsize] * num
    dis[0] = 0

    while 1:
        update = False
        for from_, to, cost in edges:
            if dis[from_] < maxsize and dis[to] > cost + dis[from_]:
                dis[to] = cost + dis[from_]
                update = True

        if not update:
            break

    for i, d in enumerate(dis):
        print(i, d)


main()
### BUGGY CODE ###

N, M, K = map(int,input().split())
MOD = 10**9+7

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

# 0~N*M-1までの1次元上と考える
ans = 0

def f(x):
    return x*(x+1)//2

c = cmb(N*M-2,K-2)

for i in range(N*M):
    tate, yoko = i//M, i%M
    migi = f(M-1-yoko)
    hidari = f(yoko)
    sita = (hidari+migi)*(N-1-tate) + M*f(N-1-tate)
    coef = migi + sita
    ans += coef*c
    ans %= MOD
print(ans)


    
    
    

### FIXED CODE ###

N, M, K = map(int,input().split())
MOD = 10**9+7

def framod(n, mod, a=1):
    for i in range(1,n+1):
        a=a * i % mod
    return a

def power(n, r, mod):
    if r == 0: return 1
    if r%2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * power(n, r-1, mod) % mod

def comb(n, k, mod):
    a=framod(n, mod)
    b=framod(k, mod)
    c=framod(n-k, mod)
    return (a * power(b, mod-2, mod) * power(c, mod-2, mod)) % mod

# 0~N*M-1までの1次元上と考える
ans = 0

def f(x):
    return x*(x+1)//2

c = comb(N*M-2,K-2,MOD)

for i in range(N*M):
    tate, yoko = i//M, i%M
    migi = f(M-1-yoko)
    hidari = f(yoko)
    sita = (hidari+migi)*(N-1-tate) + M*f(N-1-tate)
    coef = migi + sita
    ans += coef*c
    ans %= MOD
print(ans)
### BUGGY CODE ###

import math
a,b,n = map(int,input().split())
m = 0
if a-b==1:
    print(n)
elif b-a==1:
    print(n-1)
else:
    for i in range(n+1):
        ch = math.floor(a*i/b)-a*math.floor(i/b)
        m = max(m,ch)
        if m!=0 and ch==0:
            break
    print(m)


### FIXED CODE ###

import math
a,b,n = map(int,input().split())
x = min(b-1,n)
print(math.floor(a*x/b)-a*math.floor(x/b))
### BUGGY CODE ###

n=int(input())

i=1
List=[]
while i<n+1:
    if n/i==n//i:
        List.append(n//i)
    i=i+1
a=len(List)
print(List[a//2]+List[a//2-1]-2)

### FIXED CODE ###

n=int(input())

i=1
List=[]
while i<n**.5+1:
    if n/i==n//i:
        List.append(n//i)
    i=i+1
print(List[-1]+n//List[-1]-2)
### BUGGY CODE ###

def change_n_shinsu(x, n):
    ans = ''
    while True:
        shou = x // n
        amari = x % n
        if shou == 0 and amari == 0:
            break
        ans = str(amari) + ans
        x = shou
    ans = ans.zfill(60)
    return ans

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

zero = [0 for i in range(60)]
one = [0 for i in range(60)]

for i in range(n):
    ai = change_n_shinsu(a[i], 2)
    for j in range(60):
        if ai[j] == '0':
            zero[j] += 1
        else:
            one[j] += 1

zero = zero[::-1]
one = one[::-1]

ans = 0
for i in range(60):
    kumi = (zero[i] * one[i]) % mod
    num = pow(2, i, mod)
    ans += (kumi * num) % mod
    ans %= mod
print(ans)

### FIXED CODE ###

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

wa = 0
kazu = 10**9 + 7
for i in range(60):
    b = 0
    for j in a:
        b += j & 1
    wa = (wa + b*(n-b)*(1<<i)) % kazu
    for j in range(n):
        a[j] = a[j] >> 1

print(wa)
### BUGGY CODE ###

#(縦, 横)
#bfs 徒歩→ワープ→徒歩→ワープ→…

h,w = map(int,input().split())
sy, sx = map(int,input().split())
start = (sy-1, sx-1)
gy, gx = (map(int,input().split()))
goal = (gy-1, gx-1)

chizu = [input() for _ in range(h)]
kabeset = set()

for i in range(h):
	for j in range(w):
		if chizu[i][j] == "#":
			kabeset.add((i, j))

settansaku = set()
stock = set()
setmada = {start}
mode = 1
cost = 0

while len(setmada) > 0:
	while len(setmada) > 0:
		for i, j in list(setmada):
			settansaku.add((i, j))
			stock.add((i, j))
			setmada.remove((i, j))
			for k in [(i+1, j), (i-1, j), (i, j-1), (i, j+1)]:
				if not k in kabeset:
					if 0 <= k[0]:
						if 0 <= k[1]:
							if k[0] < h:
								if k[1] < w:
									if not k in setmada:
										if not k in settansaku:
											setmada.add(k)
								
	if goal in settansaku:
		mode = 0
		break
	
	cost += 1
	for i, j in list(stock):
		for k in [(i-2, j-2), (i-1, j-2), (i, j-2), (i+1, j-2), (i+2, j-2), (i-2, j-1), (i-1, j-1), (i, j-1), (i+1, j-1), (i+2, j-1), (i-2, j), (i-1, j), (i+1, j), (i+2, j), (i-2, j+1), (i-1, j+1), (i, j+1), (i+1, j+1), (i+2, j+1), (i-2, j+2), (i-1, j+2), (i, j+2), (i+1, j+2), (i+2, j+2)]:
			if not k in settansaku:
				if 0 <= k[0]:
					if 0 <= k[1]:
						if k[0] < h:
							if k[1] < w:
								if not k in kabeset:
									setmada.add(k)
	
	stock=set()
	
	if goal in settansaku:
		mode = 0
		break

if mode == 0:
	print(cost)
else:
	print(-1)

### FIXED CODE ###

h,w = map(int,input().split())
sy, sx = map(int,input().split())
start = (sy-1, sx-1)
gy, gx = (map(int,input().split()))
goal = (gy-1, gx-1)

yukaset = set()

for i in range(h):
	chizu = input()
	for j in range(w):
		if chizu[j] == ".":
			yukaset.add((i, j))

settansaku = {start}
stock = []
listmada = [start]
mode = 1
cost = 0

while len(listmada) > 0:
	for i, j in listmada:
		stock.append((i, j))
		for k in [(i+1, j), (i-1, j), (i, j-1), (i, j+1)]:
			if k in yukaset:
				if k not in settansaku:
					listmada.append(k)
					settansaku.add(k)

	if goal in settansaku:
		mode = 0
		break
	
	listmada = []
	cost += 1
	for i, j in stock:
		for k in [(i-2, j-2), (i-1, j-2), (i, j-2), (i+1, j-2), (i+2, j-2), (i-2, j-1), (i-1, j-1), (i, j-1), (i+1, j-1), (i+2, j-1), (i-2, j), (i-1, j), (i+1, j), (i+2, j), (i-2, j+1), (i-1, j+1), (i, j+1), (i+1, j+1), (i+2, j+1), (i-2, j+2), (i-1, j+2), (i, j+2), (i+1, j+2), (i+2, j+2)]:
			if k in yukaset:
				if k not in settansaku:
					listmada.append(k)
					settansaku.add(k)
	
	stock = []

if mode == 0:
	print(cost)
else:
	print(-1)
### BUGGY CODE ###

from scipy.misc import comb

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

def mycomb(a, b) :
    return int(comb(a, b, exact=True))%dekai

def usless(tukau, i) :
    if tukau-i+1 < 0 :
        return 0
    else :
        return mycomb(k-1, i-1)*mycomb(tukau-1,i-2)

def sousa(i) :
    if i == 1 :
        return n-k+1
    else :
        wa = 0
        for utan in range(n-k+1) :
            for satan in range(n-k+1-utan) :
                tukau = n-k-utan-satan
                wa += usless(tukau, i)
        return wa%dekai

for ii in range(k) :
    print(sousa(ii+1))

### FIXED CODE ###

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


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

mod = 10**9+7
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

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


for i in range(k) :
    ans = comb(n-k+1, i+1)*comb(k-1, i)%mod
    print(ans)
### BUGGY CODE ###

MOD = 10**9+7
S = input()
LenS = len(S)
DP = [[0] * 13 for _ in range(LenS+1)]

c = S[0]
if c == '?':
    for i in range(10):
        DP[1][i] = 1
else:
    n = int(c)
    DP[1][n] = 1

for i in range(2,LenS+1):
    c = S[i-1]
    if c == '?':
        for n in range(10):
            for j in range(13):
                k = (10*j+n) % 13
                DP[i][k] += DP[i-1][j] 
                DP[i][k] %= MOD
    else:
        n = int(c)  
        for j in range(13):
            k = (10*j+n) % 13
            DP[i][k] = DP[i-1][j] 
            DP[i][k] %= MOD

print(DP[LenS][5])

### FIXED CODE ###

MOD = 10**9+7
S = input()
LenS = len(S)
DP = [[0] * 13 for _ in range(LenS+1)]

c = S[0]
if c == '?':
    for i in range(10):
        DP[1][i] = 1
else:
    n = int(c)
    DP[1][n] = 1

for i in range(2,LenS+1):
    c = S[i-1]
    if c == '?':
        for n in range(10):
            for j in range(13):
                k = (10*j+n) % 13
                DP[i][k] += DP[i-1][j] 
                DP[i][k] %= MOD
    else:
        n = int(c)  
        for j in range(13):
            k = (10*j+n) % 13
            DP[i][k] = DP[i-1][j] 
            DP[i][k] %= MOD

print(DP[LenS][5])
### BUGGY CODE ###

k, s = map(int, input().split())

cnt = 0
for i in range(k+1):
  for m in range(k+1):
    for n in range(k+1):
      if i + m + n == s:
        cnt += 1
        
        
print(cnt)

### FIXED CODE ###

k, s = map(int, input().split())

cnt = 0
for x in range(k+1):
  for y in range(k+1):
    z = s - x - y
    if z >= 0 and z <= k:
      cnt += 1
        
        
print(cnt)