Harryxun/stf_run huggingface dataset:
n,t=map(int,input().split())
a=list(map(int,input().split()))
y=a[-1]+10+t
b=[0]*y
c=[0]*y
for i in a:
    b[i]+=1
    b[i+t]-=1
for i in range(len(b)):
    if i!=0:
        b[i]+=b[i-1]
d=[i for i in b if i>0]
print(len(d))


### FIXED CODE ###

n,t=map(int,input().split())
a=list(map(int,input().split()))
ans=t
for i in range(1,n):
    ans+=min(t,a[i]-a[i-1])
print(ans)
a = int(input())
b = int(input())
c = int(b - a)
d = c * (c -1) 
p = d / 2
e = int(c -1)
f = int(1 + p + e)
print(int(f - b))



### FIXED CODE ###

a, b = map(int, input().split())
c = int(b - a)
d =int( c * (c - 1) // 2 + c  -b)
print(d)
class Dice:
    def __init__(self,t,f,r,l,b,u):
        self.t = t
        self.f = f
        self.r = r
        self.l = l
        self.b = b
        self.u = u
        self.a=[t,f,r,l,b,u]
        self.direction={'S':(4,0,2,3,5,1),'N':(1,5,2,3,0,4),'E':(3,1,0,5,4,2),'W':(2,1,5,0,4,3),'Y':(0,3,1,4,2,5)}
    def roll(self,d):
        self.a=[self.a[i] for i in self.direction[d]]
        self.t = self.a[0]
        self.f = self.a[1]
        self.r = self.a[2]
        self.l = self.a[3]
        self.b = self.a[4]
        self.u = self.a[5]
t,f,r,l,b,u=map(int,input().split())
dice1=Dice(t,f,r,l,b,u)
t,f,r,l,b,u=map(int,input().split())
dice2=Dice(t,f,r,l,b,u)
s='SSSEWW'
w='YYY'
ans='No'
for j in s:
    for r in w:
        if dice1.a==dice2.a:
            ans='Yes'
            break
        dice2.roll(r)
    else:
        dice2.roll(j)
        continue
    break
print(ans)


### FIXED CODE ###

class Dice:
    def __init__(self,t,f,r,l,b,u):
        self.t = t
        self.f = f
        self.r = r
        self.l = l
        self.b = b
        self.u = u
        self.a=[t,f,r,l,b,u]
        self.direction={'S':(4,0,2,3,5,1),'N':(1,5,2,3,0,4),'E':(3,1,0,5,4,2),'W':(2,1,5,0,4,3),'Y':(0,3,1,4,2,5)}
    def roll(self,d):
        self.a=[self.a[i] for i in self.direction[d]]
        self.t = self.a[0]
        self.f = self.a[1]
        self.r = self.a[2]
        self.l = self.a[3]
        self.b = self.a[4]
        self.u = self.a[5]
t,f,r,l,b,u=map(int,input().split())
dice=Dice(t,f,r,l,b,u)
n=int(input())
s='SSSEWW'
yw='YYY'
for j in range(n):
    t,f=map(int,input().split())
    for d in s:
        if dice.t==t:
            break
        dice.roll(d)
    for t in yw:
        if dice.f==f:
            break
        dice.roll(t)
    print(dice.r)
import sys

PARTS = ["eraser", "erase", "dreamer", "dream"]


def main():
    sys.setrecursionlimit(5000)
    S = input()

    if judgeStr(S):
        print("YES")
    else:
        print("NO")


def judgeStr(target: str) -> bool:
    for item in PARTS:
        if target.startswith(item):
            tempStr = target.replace(item, "", 1)
            if tempStr == "" or judgeStr(tempStr):
                return True

    return False


if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys

PARTS = ["eraser", "erase", "dreamer", "dream"]
# PARTS2 = []


def main():
    global PARTS2
    sys.setrecursionlimit(100000)
    S = input()

    # for i in range(0, 4):
    #     for j in range(0, 4):
    #         PARTS2.append(PARTS[i] + PARTS[j])

    # PARTS2 = PARTS2 + PARTS

    if judgeStr2(S):
        print("YES")
    else:
        print("NO")


def judgeStr2(target: str) -> bool:
    currentStr = target
    while currentStr != "":
        isNextOK = False
        for item in PARTS:
            if not currentStr.startswith(item):
                continue

            tempStr = currentStr.replace(item, "", 1)
            if tempStr == "":
                return True

            for item2 in PARTS:
                if tempStr.startswith(item2):
                    isNextOK = True
                    break

            if isNextOK:
                currentStr = tempStr
                break
        if isNextOK:
            continue
        else:
            break
    return currentStr == ""


def judgeStr(target: str) -> bool:
    for item in PARTS:
        if target.startswith(item):
            tempStr = target.replace(item, "", 1)
            if tempStr == "" or judgeStr(tempStr):
                return True

    return False


if __name__ == "__main__":
    main()
import numpy as np

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

# dp[i][j][k]:
# ウサギ1~i, カメ1~i (うちj個は相手が未定)まで見ていて，
# 確定している奇妙さがkであるような場合の数
dp = np.zeros((55,55,55), dtype='int64')
dp[0][0][0] = 1

for i in range(N+1):
    for j in range(N+1):
        for k in range(N+1):
            if k-2*j < 0 or i <= 0: continue

            dp[i][j][k] += (2*j+1) * dp[i-1][j][k-2*j] % MOD
            dp[i][j][k] %= MOD

            dp[i][j][k] += (j+1)*(j+1)*dp[i-1][j+1][k-2*j] % MOD
            dp[i][j][k] %= MOD

            if j > 0:
                dp[i][j][k] += dp[i-1][j-1][k-2*j]
                dp[i][j][k] %= MOD
            
print(dp[N][0][K])

### FIXED CODE ###

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

# dp[i][j][k]:
# ウサギ1~i, カメ1~i (うちj個は相手が未定)まで見ていて，
# 確定している奇妙さがkであるような場合の数
dp = []
for _ in range(55):
    dp.append([[0] * (55*55) for _ in range(55)])

dp[0][0][0] = 1

for i in range(N+1):
    for j in range(N+1):
        for k in range(N*N+1):
            if k-2*j < 0 or i-1 < 0: continue

            dp[i][j][k] += (2*j+1) * dp[i-1][j][k-2*j] % MOD
            dp[i][j][k] %= MOD

            dp[i][j][k] += (j+1)*(j+1) * dp[i-1][j+1][k-2*j] % MOD
            dp[i][j][k] %= MOD

            if j > 0:
                dp[i][j][k] += dp[i-1][j-1][k-2*j]
                dp[i][j][k] %= MOD
            
print(dp[N][0][K])
x, y, a, b, c = map(int, input().split())
p = list(map(int, input().split()))
q = list(map(int, input().split()))
r = list(map(int, input().split()))

p = sorted(p)[a-x:]
q = sorted(q)[b-y:]
r = sorted(r, reverse=True)

pi = 0
qi = 0
ri = 0
while True:
    if ri > c-1: break
    if p[pi] < q[qi]:
        if p[pi] < r[ri]:
            p[pi] = r[ri]
            pi += 1
            ri += 1
        else:
            break
    else:
        if q[qi] < r[ri]:
            q[qi] = r[ri]
            qi += 1
            ri += 1
        else:
            break

print(sum(p)+sum(q))

### FIXED CODE ###

x, y, a, b, c = map(int, input().split())
p = list(map(int, input().split()))
q = list(map(int, input().split()))
r = list(map(int, input().split()))

p = sorted(p)[a-x:]
q = sorted(q)[b-y:]
r = sorted(r, reverse=True)

pi = 0
qi = 0
ri = 0
while True:
    if ri > c-1: break
    if pi <= x-1 and qi <= y-1:
        if p[pi] < q[qi]:
            if p[pi] < r[ri]:
                p[pi] = r[ri]
                pi += 1
                ri += 1
            else:
                break
        else:
            if q[qi] < r[ri]:
                q[qi] = r[ri]
                qi += 1
                ri += 1
            else:
                break
    elif pi <= x-1:
        if p[pi] < r[ri]:
            p[pi] = r[ri]
            pi += 1
            ri += 1
        else:
            break
    elif qi <= y-1:
        if q[qi] < r[ri]:
            q[qi] = r[ri]
            qi += 1
            ri += 1
        else:
            break
    else:
        break

print(sum(p)+sum(q))
def main():
    nmax = 10000
    n = int(input())
    values = [0] * nmax
    a = [int(v) for v in input().split()]
    for v in a:
        values[v-1] += 1
    asum = sum(a)

    q = int(input())
    for _ in range(q):
        b, c = [int(v) for v in input().split()]
        asum += values[b-1] * (c - b)
        values[c-1] += values[b-1]
        values[b-1] = 0
        print(asum)

main()

### FIXED CODE ###

def main():
    nmax = 100000
    n = int(input())
    values = [0] * nmax
    a = [int(v) for v in input().split()]
    for v in a:
        values[v-1] += 1
    asum = sum(a)

    q = int(input())
    for _ in range(q):
        b, c = [int(v) for v in input().split()]
        asum += values[b-1] * (c - b)
        values[c-1] += values[b-1]
        values[b-1] = 0
        print(asum)

main()
H, W, A, B = map(int, open(0).read().split())
MOD = 10**9+7

def modperm(m, n, mod):
    p = 1
    for i in range(n):
        p = p * (m - i) % mod
    return p

def modcomb(m, n, mod):
    if n > m - n:
        n = m - n
    p = modperm(m, n, mod)
    q = pow(modperm(n, n, mod), -1, mod)
    return p * q % mod

total = modcomb(H + W - 2, W - 1, MOD)

tmp = modcomb(A + W - 2, W - 1, MOD)
total -= tmp

for i in range(B - 1):
    a = H - A + i
    b = i + 1
    c = W - i - 1
    d = W + A - 2 - i
#     print(a,b,c,d)
    tmp = tmp * a * c % MOD
    tmp = tmp * pow(b, MOD - 2, MOD) % MOD
    tmp = tmp * pow(d, MOD - 2, MOD) % MOD
#     print(tmp)
    total = (total - tmp) % MOD

print(total)

### FIXED CODE ###

H, W, A, B = map(int, open(0).read().split())
MOD = 10**9+7

def modcomb(m, n, mod):
    if n > m - n:
        n = m - n
    p = 1
    q = 1
    for i in range(n):
        p = p * (m - i) % mod
        q = q * (i + 1) % mod
    result = p * pow(q, mod - 2, mod) % mod
    return result

total = modcomb(H + W - 2, W - 1, MOD)

tmp = modcomb(A + W - 2, W - 1, MOD)
total -= tmp

for i in range(B - 1):
    a = H - A + i
    b = i + 1
    c = W - i - 1
    d = W + A - 2 - i
#     print(a,b,c,d)
    tmp = tmp * a * c % MOD
    tmp = tmp * pow(b, -1, MOD) % MOD
    tmp = tmp * pow(d, -1, MOD) % MOD
#     print(tmp)
    total = (total - tmp) % MOD

print(total)
import sys
from bisect import bisect_left
def input():return sys.stdin.readline().strip()

def main():
    N = int(input())
    A = tuple(map(int, input().split()))

    to = [[] for _ in range(N)]
    for _ in range(N-1):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        to[u].append(v)
        to[v].append(u)
    
    ans = [0] * N
    dp = []
    def dfs(now, pre):
        a = A[now]
        idx = bisect_left(dp, a)

        if idx == len(dp):
            old = -1
            dp.append(a)
        else:
            old = dp[idx]
            dp[idx] = a
        
        ans[now] = len(dp)

        
        for nv in to[now]:
            if nv != pre:
                dfs(nv, now)
        

        if old == -1:
            dp.pop()
        else:
            dp[idx] = old

    
    dfs(0, -1)

    print(*ans, sep="\n")
        

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
from bisect import bisect_left
sys.setrecursionlimit(10**7)
def input():return sys.stdin.readline().strip()

def main():
    N = int(input())
    A = tuple(map(int, input().split()))

    to = [[] for _ in range(N)]
    for _ in range(N-1):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        to[u].append(v)
        to[v].append(u)
    
    ans = [0] * N
    dp = []
    def dfs(now, pre):
        a = A[now]
        idx = bisect_left(dp, a)

        if idx == len(dp):
            old = -1
            dp.append(a)
        else:
            old = dp[idx]
            dp[idx] = a
        
        ans[now] = len(dp)

        
        for nv in to[now]:
            if nv != pre:
                dfs(nv, now)
        

        if old == -1:
            dp.pop()
        else:
            dp[idx] = old

    
    dfs(0, -1)

    print(*ans, sep="\n")
        

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

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

def gcd(a, b):
    while b :
        a, b = b, a % b
    return a

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

L = lcm(N, M)
X = ["A"] * L

for i in range(N):
    index = i * (L // N) + 1
    X[index-1] = S[i]

for i in range(M):
    index = i * (L // M) + 1
    if X[index-1] != "A" and X[index-1] != T[i]:
        print(-1)
        sys.exit()
    X[index-1] = T[i]
    
print(L)

### FIXED CODE ###

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

def gcd(a, b):
    while b :
        a, b = b, a % b
    return a

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

L = lcm(N, M)
s = L // M
t = L // N

if S[::s] != T[::t]:
    L = -1
print(L)
#AtCodr ABC156-A

N, R = input().rstrip().split(' ')
N = int(N)
R = int(R)

if N <= 9:
    rate = R+22 3051(10-N)*100
    print(rate)
else:
    print(R)

### FIXED CODE ###

#AtCodr ABC156-A

N, R = input().rstrip().split(' ')
N = int(N)
R = int(R)

if N <= 9:
    rate = R+(10-N)*100
    print(rate)
else:
    print(R)
a=list(map(int,input().split()))
count=0
for v in range(2)
	if a[0]>=a[1]:
    	count+=a[0]
    else :
        count+=a[1]
print(count)
  

### FIXED CODE ###

a=list(map(int,input().split()))
count=0
for v in range(2):
    if a[0]>=a[1]:
        count+=a[0]
        a[0]-=1
    else:
        count+=a[1]
        a[1]-=1
print(count)
a = input()
print(a**3)
print()


### FIXED CODE ###

a = input()
a = int(a)

print( a**3)
import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@njit((i8,i8,i8[:]), cache=True)
def main(H, W, XY):
    A = np.zeros((H, W), np.int64)
    row = np.zeros(H, np.int64)
    col = np.zeros(W, np.int64)
    for i in range(0, len(XY), 2):
        x, y = XY[i:i + 2] - 1
        row[x] += 1
        col[y] += 1
        A[x, y] += 1
    ans = 0
    for h in range(H):
        for w in range(W):
            x = row[h] + col[w] - A[h, w]
            ans = max(ans, x)
    return ans

H, W, M = map(int, readline().split())
XY = np.array(read().split(), np.int64)

print(main(H, W, XY))

### FIXED CODE ###

import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@njit((i8, i8, i8[:]), cache=True)
def main(H, W, XY):
    U = 300_010
    row = np.zeros(U, np.int64)
    col = np.zeros(U, np.int64)
    for i in range(0, len(XY), 2):
        x, y = XY[i:i + 2] - 1
        row[x] += 1
        col[y] += 1
    row_max = row.max()
    col_max = col.max()
    choice = np.sum(row == row_max) * np.sum(col == col_max)
    for i in range(0, len(XY), 2):
        x, y = XY[i:i + 2] - 1
        if row[x] == row_max and col[y] == col_max:
            choice -= 1
    x = row_max + col_max
    return x if choice else x - 1

H, W, M = map(int, readline().split())
XY = np.array(read().split(), np.int64)

print(main(H, W, XY))
def main():
    N, K = map(int, input().split())
    D = set(map(int, input().split()))

    for i in range(10):
        if i not in D:
            min_ = i
            break

    ans = []
    apnd = ans.append
    num, i = N, 0
    while num > 0:
        while num % 10 in D:
            num += 1
            top = i
        num, m = divmod(num, 10)
        apnd(m)
        i += 1

    ans[0:top] = [min_] * top
    print(*ans[::-1], sep='')

main()


### FIXED CODE ###

def main():
    N, K = map(int, input().split())
    D = set(map(int, input().split()))

    for i in range(10):
        if i not in D:
            min_ = i
            break

    ans = []
    apnd = ans.append
    num, top, i = N, 0, 0
    while num > 0:
        while num % 10 in D:
            num += 1
            top = i
        num, m = divmod(num, 10)
        apnd(m)
        i += 1

    ans[0:top] = [min_] * top
    print(*ans[::-1], sep='')

main()
n = int(input())

for i in range(-1000,1000):
  for for j in range(-1000,1000):
    if i**5 - j**5 == n:
      print(i,j)
      exit()
      

### FIXED CODE ###

n = int(input())

for i in range(-1000,1000):
    for j in range(-1000,1000):
        if i**5 - j**5 == n:
            print(i,j)
            exit()
n,a,b=map(int,input().split());a+b=c;print(n//c+max(n%c-a,0))

### FIXED CODE ###

n,a,b=map(int,input().split());c=a+b;print((n//c)*a+min(n%c,a))
n,k=map(int,input().split())
hList=[]
for i in range(n):
  hList.append(int(input()))
hList.sort()
//print(hList)
ans=100000000000000
for i in range(n-k+1):
  tmp=hList[i+k-1]-hList[i]
  if(ans>tmp):
    ans=tmp
print(ans)


### FIXED CODE ###

n,k=map(int,input().split())
hList=[]
for i in range(n):
  hList.append(int(input()))
hList.sort()
#print(hList)
ans=100000000000000
for i in range(n-k+1):
  tmp=hList[i+k-1]-hList[i]
  if(ans>tmp):
    ans=tmp
print(ans)
a,b = map(int, input())
count = 1
c = 1
while c < b:
  c += a-1
  count +=1
print(count)

### FIXED CODE ###

a,b = map(int, input().split())
count = 0
c = 1
while c < b:
  c += a-1
  count +=1
print(count)
while True:
    n,w=map(int,raw_input().split())
    if n==w==0:break
    L=[0]*(w+1)
    for i in range(n):
        v=input()
        L[v/w]+=1
    maxh=max(L)
    r=n-1
    while r>0 and L[r]==0:
        r-=1
    ink=0.01
    for i in range(r+1):
        ink+=float(r-i)/r*float(L[i])/maxh
    print ink

### FIXED CODE ###

while True:
    n,w=map(int,raw_input().split())
    if n==w==0:break
    L=[0]*(w+1)
    for i in range(n):
        v=input()
        L[v/w]+=1
    maxh=max(L)
    r=w
    while r>0 and L[r]==0:
        r-=1
    ink=0.01
    for i in range(r+1):
        if r<>0:
            ink+=float(r-i)/r*float(L[i])/maxh
        else:
            ink+=L[i]
    print ink
from math import PI
r = float(raw_input())
print "%f %f" % (r*r*PI, 2*PI*r)

### FIXED CODE ###

from math import pi
r = float(raw_input())
print "%f %f" % (r*r*pi, 2*pi*r)
import sys
import heapq  # heapqライブラリのimport

stdin = sys.stdin
 
ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

N, C = rl()
STC = [[] for _ in range(C+1)]

for _ in range(N):
    s, t, c = rl()
    STC[c].append((s, t))

for i in range(1, C+1):
    stc = STC[i]
    for j in range(1, len(stc)):
        if stc[j][0] == stc[j-1][1]:
            stc[j] = (stc[j-1][0], stc[j][1])
            stc.pop(j-1)
    STC[i] = stc

program = []
for stc_list in STC:
    for s, t in stc_list:
        program.append((s, t))

program.sort()

recorder = [-1]
heapq.heapify(recorder)

for s, t in program:
    if s-0.5 > recorder[0]:
        heapq.heappop(recorder)
    heapq.heappush(recorder, t)

print(len(recorder))


### FIXED CODE ###

import sys
import heapq  # heapqライブラリのimport

stdin = sys.stdin
 
ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

N, C = rl()
STC = [[] for _ in range(C+1)]

for _ in range(N):
    s, t, c = rl()
    STC[c].append((s, t))

for i in range(1, C+1):
    stc = STC[i]
    stc.sort()
    p = []
    for j in range(1, len(stc)):
        if stc[j][0] == stc[j-1][1]:
            stc[j] = (stc[j-1][0], stc[j][1])
            p.append(j-1)
    for x in p[::-1]:
        stc.pop(x)
    STC[i] = stc

program = []
for stc_list in STC:
    for s, t in stc_list:
        program.append((s, t))

program.sort()

recorder = [-1]
heapq.heapify(recorder)

for s, t in program:
    if s-0.5 > recorder[0]:
        heapq.heappop(recorder)
    heapq.heappush(recorder, t)

print(len(recorder))
N=int(input())
lst=list(map(int,input().split()))
lst.sort(reverse=True)

A=0
B=0
for i in range(N):
    if i==0 or i%2==0:
        A+=lst[i]
    else:
        B+=lst[i]

print(int(A)-int(B))

### FIXED CODE ###

N=int(input())
A=int(input())

a=int(N%500)
if A>=a:
    print("Yes")
else:
    print("No")
def f(x,y):
	if x*y < 0:
		return min(f(-x,y),f(y,-x))
	else:
		return x-y+2 if x>y else x-y
print(f(list(map(int,input().split()))))

### FIXED CODE ###

x,y = map(int,input().split())
def f(a):
	m = float('inf')
	for i in a:
		if i >= 0:
			m = min(i,m)
	return m
print(f([y-x,y+x+1,-x-y+1,x-y+2]))
# A
K = int(input())
A, B = map(int,input().split())

if(A%K==0 or B%K==0 or (B-A>=K and B!=A):
    print('OK')
else:
    print('NG')

### FIXED CODE ###

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

if(A%K==0 or B%K==0):
    print('OK')
elif(B-A >= K - A%K):
    print('OK')
else:
    print('NG')
import sys
if sys.version_info[0]>=3: raw_input=input

n=int(raw_input())
for i in range(0,n):
	a=map(int,raw_input().split())
	a[0]-=1;a[1]-=1
	print(196471-a[0]*195-a[0]/3*5-a[1]*20+(a[1]/2 if a[0]%3!=2 else 0)-a[2])

### FIXED CODE ###

import sys
if sys.version_info[0]>=3: raw_input=input

n=int(raw_input())
for i in range(0,n):
	a=[int(e) for e in raw_input().split()]
	a[0]-=1;a[1]-=1
	print(196471-a[0]*195-a[0]//3*5-a[1]*20+(a[1]//2 if a[0]%3!=2 else 0)-a[2])
print("Aa"[ord(input())>95)


### FIXED CODE ###

print("Aa"[ord(input())>95])
num = 1
for i in int(input()):
    if i == 0:
        break
    print(f"Case {num}: {i}")
    num +=1

### FIXED CODE ###

num = 1
while True:
    x = int(input())
    if x == 0: break
    print ("Case {0}: {1}".format(num,x))
    num += 1
S = input()
if S = 'AAA' or S = 'BBB':
  print('No')
else:
  print('Yes')
  

### FIXED CODE ###

S = input()
if (S == 'AAA') or (S == 'BBB'):
  print('No')
else:
  print('Yes')
n, m = map(int, input().split())
D = [list() for i in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    D[a-1].append(b-1)
    D[b-1].append(a-1)

d = [0]*n
d[0] = 1
cnt = 0


def dfs(x):
    global cnt
    if all(d):
        cnt += 1
        return
    for i in D[x]:
        if d[i] == 0:
            d[i] = 1
            dfs(i)
            d[i] = 0


dfs(0)
print(cnt)
n, m = map(int, input().split())
D = [list() for i in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    D[a-1].append(b-1)
    D[b-1].append(a-1)

d = [0]*n
d[0] = 1
cnt = 0


def dfs(x):
    global cnt
    if all(d):
        cnt += 1
        return
    for i in D[x]:
        if d[i] == 0:
            d[i] = 1
            dfs(i)
            d[i] = 0


dfs(0)
print(cnt)

### FIXED CODE ###

N, M = map(int, input().split())
r = [[] * N for i in range(N)]
reached = [0] * N
reached[0] = 1
count = 0
 
def dfs(now):
    global count
    if all(reached):
        count += 1
    for next in r[now]:
        if reached[next] == 0:
            reached[next] = 1
            dfs(next)
            reached[next] = 0
 
for i in range(M):
    a, b = map(lambda x: int(x) - 1, input().split())
    r[a].append(b)
    r[b].append(a)
 
dfs(0)
 
print(count)
N,M=(map(int,input().split()))

C=[input().split() for i in range(N)]
B=[]
for i in C:
    B.append(list(map(int,i)))

B.sort()

k=0
l=0#何番目の店
m=0#その店で買う数
money=0
X=0#持ち数

while M>X:
    money+=B[0][0]*B[0][1]
    X+=B[0][1]
    if M<X:
        money-=B[0][0]*B[0][1]
        X-=B[0][1]
        for x in range(B[0][1]):
            m+=1
            if M=X+m:
                money+=B[0][0]*m
                print(money)
                break

    B.pop(l)#取り出す


### FIXED CODE ###

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

C=[input().split() for i in range(N)]
B=[]
for i in C:
    B.append(list(map(int,i)))

B.sort()

k=0
l=0#何番目の店
m=0#その店で買う数
money=0
X=0#持ち数
for a,b in B:
    if(M<=0):
        break
    if(b<=M):
        money+=a*b
    else:
        money+=M*a
    M-=b
print(money)
# -*- coding: utf-8 -*-

N, L = map(int, input().split())
str_list = [input() for i in range(L)]

str_list.sort()

ans = ""
for i in range(L):
    ans += str_list[i]

print(ans)

### FIXED CODE ###

# -*- coding: utf-8 -*-

N, L = map(int, input().split())
str_list = [input() for i in range(N)]

str_list.sort()

ans = ""
for i in range(N):
    ans += str_list[i]

print(ans)
N, K = map(int, input().split())
R = N - K
mod = pow(10, 9) + 7

N += 1

fact = [0] * N
inv = [0] * N
inv_cal = [0] * N

fact[:2] = [1, 1]
inv[1] = 1
inv_cal[:2] = [1, 1]

for i in range(2, 2001):
    fact[i] = fact[i-1] * i % mod
    inv[i] = mod - (mod // i) * inv[mod % i] % mod
    inv_cal[i] = inv_cal[i-1] * inv[i] % mod

def comb(n, k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fact[n] * (inv_cal[k] * inv_cal[n-k] % mod) % mod

for k in range(1, K+1):
    print(comb(R+1, k) * comb(K-1, k-1) % mod)

### FIXED CODE ###

N, K = map(int, input().split())
R = N - K
mod = pow(10, 9) + 7

fact = [0] * 2001
inv = [0] * 2001
inv_cal = [0] * 2001

fact[:2] = [1, 1]
inv[1] = 1
inv_cal[:2] = [1, 1]

for i in range(2, 2001):
    fact[i] = fact[i-1] * i % mod
    inv[i] = mod - (mod // i) * inv[mod % i] % mod
    inv_cal[i] = inv_cal[i-1] * inv[i] % mod

def comb(n, k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fact[n] * (inv_cal[k] * inv_cal[n-k] % mod) % mod

for k in range(1, K+1):
    if R+1 >= k:
        print(comb(R+1, k) * comb(K-1, k-1) % mod)
    else:
        print(0)