Harryxun/stf_run huggingface dataset:
class Factorial():
    def __init__(self,n,mod):
        self.mod = mod
        self.factorial = [0 for _ in range(n+1)]
        self.inv = [0 for _ in range(n+1)]
        self.factorial[0] = 1
        self.inv[0] = 1
        for i in range(n):
            self.factorial[i+1] = self.factorial[i]*(i+1)%mod
        self.inv[n] = pow(self.factorial[n],mod-2,mod)
        for i in range(n)[::-1]:
            self.inv[i] = self.inv[i+1]*(i+1)%mod
            
    def comb(self,m,k):
        return self.factorial[m]*self.inv[k]*self.inv[m-k]%self.mod

def factorization(n):
    if n == 1: return [1]
    res = []
    x = n
    y = 2
    while y*y <= x:
        while x % y == 0:
            res.append(y)
            x //= y
        y += 1
    if x > 1: res.append(x)
    return res

from collections import Counter

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

ans = 1

if M > 1:

    F = factorization(M)
    C = Counter(F)

    fact = Factorial(2*N,MOD)
    
    for v in C.values():
        ans *= fact.comb(N+v-1,v)
        ans %= MOD

print(ans)

### FIXED CODE ###

from operator import mul
from functools import reduce

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i == 0:
            cnt = 0
            while temp%i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])
    if temp != 1:
        arr.append([temp, 1])
    if arr == []:
        arr.append([n, 1])
    return arr

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under 
    
n,m = map(int,input().split())

f = factorization(m)
c = 1

for i in range(len(f)):
  c *= cmb(n+f[i][1]-1,f[i][1])%1000000007

if m != 1:
  print(c%1000000007)
else:
  print(1)
n = int(input())
a = list(map(int,input().split()))
a.sort(reverse = True)
Alice = sum(a[::2])
Bob = sum(a[1::2])
print(Alice - )

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
list.sort(a,reverse = True)
k = 0
l = 0

for i in range(n)[::2]:
    k += a[i]

for i in range(n)[1::2]:
    l += a[i]

print(k - l)
S = input()
if “a” in S and “b” in S and “c” in S:
    print(“Yes”)
else:
    print(“No”)


### FIXED CODE ###

s = input()
if "a" in s and "b" in s and "c" in s:
	print("Yes")
else:
	print("No")
import math
from functools import reduce

def lcm_base(x, y):
    return (x * y) // math.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

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

m = lcm(*a) - 1

f = 0
for ai in a:
    f = f + m%ai

print(f)

### FIXED CODE ###

import fractions
from functools import reduce

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

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

# gcd = functools.reduce(math.gcd, values)
m = reduce(lcm, a) - 1

f = 0
for ai in a:
    f = f + m%ai

print(f)
import sys
import os

S = input()
K = int(input())

cnt = 1
ans = 0
i = 0
while i < len(S)-1:
    for j in range(i+1,len(S)):
        if S[i] == S[j]:
            cnt +=1
        else:
            i = j
            break
    if cnt > 1:
        ans += cnt//2
        cnt = 1
        i = j
ans = K*ans
if S[0] == S[-1]:
    if S[0] != S[1] and S[-2] != S[-1]:
        ans += K-1
print(ans)


### FIXED CODE ###

import sys
S = input()
K = int(input())
if len(S) == 1:
    print(K//2)
    sys.exit()
cnt0 = 1
cntL = 1
cnt = 1
ans = 0
i = 0
while i < len(S)-1:
    for j in range(i+1,len(S)):
        if S[i] == S[j]:
            cnt +=1
        else:
            if i == 0:
                cnt0 = cnt
            i = j
            break
    if cnt > 1:
        ans += cnt//2
        cnt = 1
        i = j

for i in range(len(S)-1,0,-1):
    if S[i] == S[i-1]:
        cntL +=1
    else:
        break
ans = K*ans
if S[0] == S[-1] and cnt0%2 != 0 and cntL %2 != 0:
    ans += K-1
if cntL == len(S):
    if (K*cntL)%2==0:
        print((K*cntL)//2)
    else:
        print((K*cntL-1)//2)
    sys.exit()
print(ans)
n, k = map(int, input().split())
p = list(map(int, input().split()))

max_x = 0
idx = 0
x = 0

for i in range(n-k):
    x += p[i+k] - p[i]
    if max_x < x:
        max_x = x
        idx = i

ans = (sum(p[i:i+k]) + k) / 2
print(ans)

### FIXED CODE ###

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

max_x = 0
idx = 0
x = 0

if n == k:
    print((sum(p) + k) / 2)
    exit()

for i in range(n-k):
    x += p[i+k] - p[i]
    if max_x < x:
        max_x = x
        idx = i+1

ans = (sum(p[idx:idx+k]) + k) / 2
print(ans)
import math


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

D = math.inf
R = 0

for i, h in enumerate(H):
    d = A - (T - h * 0.006)
    if D > d:
        D = d
        R = i + 1

print(R)


### FIXED CODE ###

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

D = 99999999
R = 0

for i, h in enumerate(H):
    d = abs(A - (T - h * 0.006))
    if D > d:
        D = d
        R = i + 1

print(R)
a,b = map(int, input().split())
i = 0
while i<=a:
  turu = 2*(a-i)
  kame = 4*i
  
  if b == turu:
    print('YES')
    
  if b == kame:
    print('YES')
  
  amari = b - turu
  if amari == 0:
    print('YES')
    break

  if kame !=0:
    if amari % kame == 0:
      print('YES')
      break
      
  i = i + 1
  
else:
  print('No)

### FIXED CODE ###

a,b = map(int, input().split())
i = 0
while i<=a:
  turu = 2*(a-i)
  kame = 4*i
  ans = turu + kame
  if ans == b:
    print('Yes')
    break
  i = i + 1
  
else:
  print('No')
from functools import reduce
import math

def lcm_base(x, y):
    return (x * y) // math.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

N = int(input().rstrip())
As = input().rstrip().split(" ")
As = [int(p) for p in As]

cand = lcm_list(As)

sum = 0

for num in As:
    sum = sum + cand / num

print(int(sum % (10**9 + 7)))


### FIXED CODE ###

from functools import reduce
import fractions

def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

N = int(input().rstrip())
As = input().rstrip().split(" ")
As = [int(p) for p in As]

cand = lcm_list(As)

sum = 0

for num in As:
    sum = sum + cand // num

print(sum % int(1e9+7) )
def solve(n, a):
    """
    References
    ----------
    [1]. 足跡-sokuseki-, CODE FESTIVAL 2016 Grand Final C - Cheating Nim, http://wk1080id.hatenablog.com/entry/2018/08/17/234023
    [2]. iroiro, CODE FESTIVAL 2016 Grand Final C - Cheating Nim, http://xxxasdfghjk999.hatenablog.jp/entry/2018/11/01/235259
    [3]. Yang33, 競プロにおけるNim、Grundy数とNimK, http://yang33-kassa.hatenablog.com/entry/2017/12/21/202812
    """
    x = 0
    for i in range(n):
        x ^= a[i]
    b = [a[i] ^ (a[i] - 1) for i in range(n)]
    mapping = {2**k-1: 0 for k in range(30)}
    for y in b:
        mapping[y] += 1
    ans = 0
    for k in range(30, 0, -1):
        y = 2**k - 1
        z = 2**(k-1)
        if (x & z) > 0 and (mapping[y] > 0):
            ans += 1
            mapping[y] -= 1
            x ^= y
    return ans if x == 0 else -1

n = int(input())
a = [int(input()) for i in range(n)]
print(solve(n, a))

### FIXED CODE ###

def solve(n, a):
    """
    References
    ----------
    [1]. 足跡-sokuseki-, CODE FESTIVAL 2016 Grand Final C - Cheating Nim, http://wk1080id.hatenablog.com/entry/2018/08/17/234023
    [2]. iroiro, CODE FESTIVAL 2016 Grand Final C - Cheating Nim, http://xxxasdfghjk999.hatenablog.jp/entry/2018/11/01/235259
    [3]. Yang33, 競プロにおけるNim、Grundy数とNimK, http://yang33-kassa.hatenablog.com/entry/2017/12/21/202812
    """
    x = 0
    for i in range(n):
        x ^= a[i]
    b = [a[i] ^ (a[i] - 1) for i in range(n)]
    mapping = {2**k-1: 0 for k in range(31)}
    for y in b:
        mapping[y] += 1
    ans = 0
    for k in range(30, 0, -1):
        y = 2**k - 1
        z = 2**(k-1)
        if (x & z) > 0 and (mapping[y] > 0):
            ans += 1
            mapping[y] -= 1
            x ^= y
    return ans if x == 0 else -1

n = int(input())
a = [int(input()) for i in range(n)]
print(solve(n, a))
N = int(input())
E = [[] for _ in range(N+1)]
for n in range(N-1):
    a,b = map(int, input().split())
    E[a].append((b,n))
    E[b].append((a,n))

K = max(len(e) for e in E)
print(K)

res = [-1 for _ in range(N-1)]
def dps(v=1, p=0, p_col=-1):
    col = 1
    for child, idx in E[v]:
        if(child != p):
            if(col == p_col):
                col += 1
            res[idx] = col
            dps(child,v,col)
            col += 1
dps()
print("\n".join(map(str, res)))


### FIXED CODE ###

import sys
sys.setrecursionlimit(500000)
N = int(input())
E = [[] for _ in range(N+1)]
for i in range(N-1):
    a, b = map(int, input().split())
    E[a].append((b, i))
    E[b].append((a, i))
K = max(len(e) for e in E)
print(K)
Ans = [-1] * (N-1)
def dfs(v=1, p=0, p_col=-1):
    col = 1
    for u, idx in E[v]:
        if u!=p:
            if col == p_col:
                col += 1
            Ans[idx] = col
            dfs(u, v, col)
            col += 1
dfs()
print("\n".join(map(str, Ans)))
s = input()
if s[3] == s[4]:
	if s[5] == s[6]:
  	    print("Yes")
else:
	print("No")

### FIXED CODE ###

s = input()
if s[2]==s[3] and s[4]==s[5]:
	print("Yes")
else:
	print("No")
n = int(input())

if n < int("1" + "9"*(len(str(n))-1)):
	s = 9*(len(str(n))-1)
else:
	for i in range(1,10)[::-1]:
		if n > int(str(i) + "9"*(len(str(n))-1)):
			s = i + 9*(len(str(n))-1)
			break

print(s)

### FIXED CODE ###

n = int(input())

for i in range(10)[::-1]:
	if n >= int(str(i) + '9'*(len(str(n))-1)):
		print(i + 9*(len(str(n))-1))
		break
from collections import Counter

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

c = Counter(A)
pair = []
print(c)
for x, cnt in c.items():
    pair += [x] * (cnt//2)

# print(pair)
pair.sort()

ans = 0
if len(pair) >= 2:
    ans = pair[-1] * pair[-2]
print ans

### FIXED CODE ###

from collections import Counter

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

c = Counter(A)
pair = []
# print(c)
for x, cnt in c.items():
    pair += [x] * (cnt//2)

# print(pair)
pair.sort()

ans = 0
if len(pair) >= 2:
    ans = pair[-1] * pair[-2]
print(ans)
#129c
import sys
sys.setrecursionlimit(10000)

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

now_step = 0
ans = 1
calculated_jump = {}
mod_number = 1000000007 

#開いている段数の移動パターンを算出する関数
def jump(now_step):
    
    if now_step in calculated_jump:
        return calculated_jump[now_step]
    else:
        if now_step == 2:
            return 2
        elif now_step == 1:
            return 1
        else:
            if now_step not in calculated_jump:
                calculated_jump[now_step] = jump(now_step-1) + jump(now_step-2)
                return jump(now_step-1) + jump(now_step-2)

for _ in range(M):
    a = int(input())
    
    if a == now_step:
        print("0")
        break
    elif a - 1 - now_step != 0: #左記成立時は1通りしかない。
        target_step_count = a - 1 - now_step #aは踏んではいけない段なので、その前がターゲット
        ans = ans * jump(target_step_count)
            
    now_step = a + 1

else:
    if now_step != N:
        target_step_count = N - now_step
        ans = ans * jump(target_step_count)
    
    print(ans % mod_number)

### FIXED CODE ###

#129c
import sys
sys.setrecursionlimit(1000000)

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

now_step = 0
ans = 1
calculated_jump = {}
mod_number = 1000000007 

#開いている段数の移動パターンを算出する関数
def jump(now_step):
    
    if now_step in calculated_jump:
        return calculated_jump[now_step]
    else:
        if now_step == 2:
            return 2
        elif now_step == 1:
            return 1
        else:
            if now_step not in calculated_jump:
                calculated_jump[now_step] = jump(now_step-1) + jump(now_step-2)
                return jump(now_step-1) + jump(now_step-2)

for _ in range(M):
    a = int(input())
    
    if a == now_step:
        print("0")
        break
    elif a - 1 - now_step != 0: #左記成立時は1通りしかない。
        target_step_count = a - 1 - now_step #aは踏んではいけない段なので、その前がターゲット
        ans = ans * jump(target_step_count) % mod_number
            
    now_step = a + 1

else:
    if now_step != N:
        target_step_count = N - now_step
        ans = ans * jump(target_step_count) % mod_number
    
    print(ans)
a, b = map(int, input().split())
c = list(map(int, input().split()))
d = [0] * 45
for i in c:
    e = bin(i)[2:]
    for j in range(len(e)):
        d[j] += 1 if e[-j-1] == "1" else 0
ans = 0
s = 0
for i in range(44, -1, -1):
    if 2 ** i + s <= b
        if a > d[i] * 2:
            s += 2 ** i
for i in c:
    ans += i ^ s
print(ans)


### FIXED CODE ###

a, b = map(int, input().split())
c = list(map(int, input().split()))
d = [0] * 45
for i in c:
    e = bin(i)[2:]
    for j in range(len(e)):
        d[j] += 1 if e[-j-1] == "1" else 0
e = 0
for i in range(len(d)-1, -1, -1):
    if 2 ** i + e <= b:
        if d[i] <= len(c) // 2:
            e += 2 ** i
f = 0
for i in range(len(c)):
    f += e ^ c[i]
print(f)
a,b,c = map(int,input.split())
print = min(a*b , c)

### FIXED CODE ###

a,b,c = map(int,input().split())
print(min(a*b , c))
import math
N, K = [int(t) for t in input().split()]
A = [int(t) for t in input().split()]

idx = A.index(1)
left = A[:idx+1]
right = A[idx:]


def get_cnt(L):
    return math.ceil((len(L) - 1) / (K-1))


if left + 1 < K or N - right < K:
    print(get_cnt(A))
else:
    print(get_cnt(left) + get_cnt(right))


### FIXED CODE ###

import math
N, K = [int(t) for t in input().split()]
A = [int(t) for t in input().split()]

print(math.ceil((N - 1) / (K-1)))
n = input()
s = input().split()
s=[int(i) for i in s]
count=-1
for i in range(int(n)//2):
   if s[i] + s[count] ==int(n)+1:
      count-=1
   	else:
      print("No")

if int(n) %2 ==0：
   print("YES")
else:
   if s[count]*2 == n :
    print("YES")
    else:
      print("NO")
  

### FIXED CODE ###

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

count=0
for i in range(int(n)):
  if N[i] !=i+1:
    count+=1
if count > 2:
  print("NO")
else:
  print("YES")
import sys
from collections import deque
sys.setrecursionlimit(10 ** 5 + 10)

N = int(input())

branch = [[0] + list(map(lambda x: int(x) - 1, input().split())) for _ in range(N - 1)]
branch_color = [0] * (N - 1)
vertex = [False] * N


def bfs():
    q = deque()
    v = 0
    bc = 0
    q.append((v, bc))

    while len(q):
        v, bc = q.popleft()
        vertex[v] = True
        b_list = [c for c in branch if v in c[1:]]

        for i in [x for x in range(len(b_list)) if x != bc]:
            if (b_list[i][0] == 0):
                b_list[i][0] = i

        for b in b_list:
            nv = b[1] if b[2] == v else b[2]
            if vertex[nv] is False:
                q.append(nv)


bfs()
for b in branch:
    print(b[0])


### FIXED CODE ###

import sys


sys.setrecursionlimit(10 ** 6)

N = int(input())
edge = [[] for _ in range(N)]
for i in range(N - 1):
    a, b = map(int, input().split())
    edge[a - 1].append((b - 1, i))
    edge[b - 1].append((a - 1, i))
ec = [0] * (N - 1)


def dfs(node, pc):
    color = 1

    for to, idx in edge[node]:
        if ec[idx] == 0:
            if color == pc:
                color += 1
            ec[idx] = color

            dfs(to, color)
            color += 1


dfs(0, -1)
print(max(ec))
for c in ec:
    print(c)
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    h,w=map(int,input().split())
    A=[input() for _ in range(h)]
    dp=[[0]*w for _ in range(h)] #(i,j)までの経路の総数
    dp[0][0]=1
    mod=10**9+7
    for i in range(h):
        for j in range(w):
            if A[i][j]=="#":continue
            if i>=1 and j>=1:    
                dp[i][j]+=(dp[i-1][j]+dp[i][j-1])%mod
            elif j==0:
                dp[i][j]+=dp[i-1][j]%mod
            else:
                dp[i][j]+=dp[i][j-1]%mod
    print(dp[-1][-1]%mod)

if __name__=='__main__':
    main()

### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()
def multi_mat(M1,M2,n,mod=10**9+7):
    ans=[[0]*n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            for k in range(n):
                ans[i][j]=(ans[i][j]+M1[i][k]*M2[k][j])%mod
    return ans
def pow_mat(M,k,n,mod=10**9+7):
    ans=[[0]*n for _ in range(n)]
    for i in range(n):ans[i][i]=1
    while k:
        if k%2:ans=multi_mat(ans,M,n,mod)
        M=multi_mat(M,M,n,mod)
        k//=2
    return ans

def main():
    n,k=map(int,input().split())
    A=[[int(_) for _ in input().split()] for i in range(n)]
    mod=10**9+7
    Ax=pow_mat(A,k,n,mod)
    print(sum(sum(x)%mod for x in Ax)%mod)

if __name__=='__main__':
    main()
import pandas as pd
n=int(input())
O=[]
A=[]
B=[]
for i in range(n):
    a,b=map(int, input().split(" "))
    O.append(a+a-b)
    A.append(a)
    B.append(b)

tmp=pd.DataFrame()
tmp["o"]=O
tmp["b"]=A
tmp["c"]=B

tmp=tmp.sort_values(by="o",ascending=False)

count=0
for num,(i,j) in enumerate(zip(tmp["b"].values,tmp["c"].values)):
    if num%2==0:
        count+=i
    else:
        count-=j
print(count)



### FIXED CODE ###

#import pandas as pd
n=int(input())
O=[]
#A=[]
#B=[]
for i in range(n):
    a,b=map(int, input().split(" "))
    O.append([a+b,a,b])
  
#O=sorted(O, key=lambda x: (x[0],x[1]))[::-1]
O=sorted(O, key=lambda x: (x[0]))[::-1]
#print(O)

count=0
for num in range(n):
    if num%2==0:
        count+=O[num][1]
    else:
        count-=O[num][2]

print(count)
n = int(input())
x = 0
mn = 101
for i in range(n):
    s = int(input())
    x += s
    if x % 10 != 0
        if s < mn:
            mn = s
if x % 10 != 0:
    print(x)
else:
    x -= mn
    if x % 10 == 0:
        print(0)
    else:
        if x < 0:
            print(0)
            exit()
        print(x)
        

### FIXED CODE ###

n = int(input())
x = 0
mn = 100
for i in range(n):
  s = int(input())
  x += s
  if s % 10 != 0:
    if s <= mn:
      mn = s
if x % 10 != 0:
  print(x)
else:
  x -= mn
  if x % 10 == 0:
    print(0)
  else:
    if x < 0:
      print(0)
      exit()
    print(x)
N, M = map(int, input().split())
edge = [[] for _ in range(N)]
for i in range(M):
    a,b = map(int, input().split())
    edge[a-1].append(b-1)

def dp(v,dpv,e):
    if dpv[v] != -1:
        return dpv[v]
    if len(e[v])==0:
        dpv[v]=0
        return 0
    res = 0
    for w in e[v]:
        res = max(dp(w,dpv,e),res)
    res += 1
    dpv[v] = res
    return res

def solve(edge):
    dpv = [-1]*N
    for i in range(N):
        dp(i,dpv,edge)
    ans = max(dpv)
    return ans
print(solve(edge))

### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)
N, M = map(int, input().split())
edge = [[] for _ in range(N)]
for i in range(M):
    a,b = map(int, input().split())
    edge[a-1].append(b-1)

def dp(v,dpv,e):
    if dpv[v] != -1:
        return dpv[v]
    if len(e[v])==0:
        dpv[v]=0
        return 0
    res = 0
    for w in e[v]:
        res = max(dp(w,dpv,e),res)
    res += 1
    dpv[v] = res
    return res

def solve(edge):
    dpv = [-1]*N
    for i in range(N):
        dp(i,dpv,edge)
    ans = max(dpv)
    # print(dpv)
    return ans
print(solve(edge))
n = int(input())
a = list(map(int, input()))

money = 1000
for i in range(n-1):
  if a[i] < a[i+1]:
    money += (a[i-1]-a[i]) * (money//a[i])
print(money)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
 
money = 1000
for i in range(n-1):
  if a[i] < a[i+1]:
    money += (a[i+1]-a[i]) * (money//a[i])
print(money)
S = str(input())
w = int(input())
idx = w
ans = ""
while idx <= len(S):
  ans += S[idx]
  idx += w
print(ans)

### FIXED CODE ###

S = str(input())
w = int(input())
idx = 0
ans = ""
while idx < len(S):
  ans += S[idx]
  idx += w
print(ans)
a, b, c, d = map(int, input().split())
for op1 in ['+', '-']:
    for op2 in ['+', '-']:
        for op3 in ['+', '-']:
            ans = a
            if op1 == '+':
                ans += b
            else:
                ans -= b
            if op2 == '+':
                ans += c
            else:
                ans -= c
            if op3 == '+':
                ans += d
            else:
                ans -= d
            if ans == 7:
                print(str(a) + op1 + str(b) + op2 + str(c) + op3 + str(d))
                exit()

### FIXED CODE ###

a, b, c, d = [int(i) for i in input()]
for op1 in ['+', '-']:
    for op2 in ['+', '-']:
        for op3 in ['+', '-']:
            ans = a
            if op1 == '+':
                ans += b
            else:
                ans -= b
            if op2 == '+':
                ans += c
            else:
                ans -= c
            if op3 == '+':
                ans += d
            else:
                ans -= d
            if ans == 7:
                print(str(a) + op1 + str(b) + op2 + str(c) + op3 + str(d) + '=7')
                exit()
import math


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


def resolve():
    N, K = map(int, input().split())
    const = 1e9 + 7
    n_iter = int(min(K, N - K + 1))
    for i in range(1, K + 1):
        ans = combinations_count(N - K + 1, i) * combinations_count(
            K - 1, i - 1)
        print(int(ans % const))
resolve()

### FIXED CODE ###

import math


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


def resolve():
    N, K = map(int, input().split())
    const = 1e9 + 7
    for i in range(1, K + 1):
        if (N - K + 1 >= i):
            print(
                combinations_count(N - K + 1, i) *
                combinations_count(K - 1, i - 1) % 1000000007)
        else:
            print(0)
            
resolve()
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
N, M, P = map(int, input().split())
e = dd(list)
for _ in range(M):
  a, b, c = map(int, input().split())
  e[a].append((b, -c + P))
class BellmanFord:
  def __init__(self, n, e):
    self.n = n
    self.edges = []
    self.b = pow(10, 10)
    for k in e.keys():
      for t in e[k]:
        self.edges.append(k * pow(b, 2) + t[0] * b + t[1])
  def path(self, s, t):
    d = [float("inf")] * (self.n + 1)
    d[s] = 0
    b = self.b
    for i in range(self.n + 1):
      for x in self.edges:
        u = x // pow(b, 2)
        v = x // b - u * b
        c = x % b
        if d[u] != float("inf") and (d[u] + c < d[v]):
          d[v] = d[u] + c
    return d[t]
  def path_findloop(self, s, t):
    d = [float("inf")] * (self.n + 1)
    d[s] = 0
    first = 0
    b = self.b
    for i in range(1, self.n * 2 + 1):
      for x in self.edges:
        u = x // pow(b, 2)
        v = x // b - u * b
        c = x % b
        print(u, v, c)
        if u != float("inf") and (d[u] + c < d[v]):
          d[v] = d[u] + c
          if i > N: d[v] = -float("inf")
      if i == self.n:
        first = d[t] + 0
      elif i == self.n * 2:
        if first != d[t]:
          return "-loop"
    return d[t]
bf = BellmanFord(N, e)
res = bf.path_findloop(1, N)
print(res)
if res == "-loop": print(-1)
else: print(max(0, -res))

### FIXED CODE ###

import collections
import sys
import time
sys.setrecursionlimit(10 ** 5)
N, M, P = map(int, input().split())
e = collections.defaultdict(list)
st = time.time()
for _ in range(M):
  u, v, c = map(int, input().split())
  e[u].append((v, c))
def isConnected(n):
  if n == N:
    return True
  vis = [0] * (N + 1)
  que = collections.deque([])
  que.append(n)
  while que:
    nc = que.popleft()
    vis[nc] = 1
    for o in e[nc]:
      if o[0] == N:
        return True
      if vis[o[0]] == 0:
        que.append(o[0])
  return False
inf = 10 ** 10
visited = [0] * (N + 1)
earn = [-inf] * (N + 1)
earn[1] = 0
def dfs(now):
  global visited
  global earn
  nt = time.time() - st
  if nt > 1.95:
    print(max(earn[N], 0))
    exit(0)
  visited[now] = 1
  for n in e[now]:
    if visited[n[0]] == 0:
      if n[1] + earn[now] - P > earn[n[0]]:
        earn[n[0]] = n[1] + earn[now] - P
        dfs(n[0])
        visited[n[0]] = 0
    else:
      if earn[n[0]] < n[1] + earn[now] - P:
        if isConnected(n[0]) == True:
          print(-1)
          exit(0)
dfs(1)
print(max(earn[N], 0))