Harryxun/stf_run huggingface dataset:
import bisect
import sys
MAX_INT = int(10e12)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(100000000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

def tami(index):
  if index == N:
    ans.append(-1)
    return
  num = a[index]
  if len(data[num]) == 1:
    ans.append(index)
    tami(index+1)
  elif index == data[num][-1]:
    ans.append(index)
    tami(data[num][0] +1)
  else:
    tmp = bisect.bisect_right(data[num],index)
    #print(num,data[num],tmp)
    tami(data[num][tmp]+1)

def judge(x):
  d = []
  d.append(a[x])
  while True:
    x += 1
    if x == N:
      break
    if len(data[a[x]]) == 1:
      d.append(a[x])
    elif x == data[a[x]][-1]:
      d.append(a[x])
    else:
      tmp = bisect.bisect_right(data[a[x]],x)
      x = data[a[x]][tmp]
  return d

N,K = IL()
a = IL()

data = [[] for i in range(N+1)]
ans = []

for i in range(N):
  data[a[i]].append(i)

#print(data)

tami(0)
#print(ans)
#print(len(ans),K)
#print(K%len(ans))

if ans == [-1] or K%len(ans) == 0:
  print()
else:
  print(" ".join(map(str,(judge(ans[K%len(ans)-1])))))
"""
for i in range(K):
  for j in range(N):
    if a[j] in data:
      num = data.index(a[j])
      data = data[:num]
    else:
      data.append(a[j])
  print(data)

11 10
1 2 3 0 4 5 6 0 4 5 6

11 10
3 1 4 1 5 9 2 6 5 3 5

10 10
1 4 8 3 5 4 2 3 4 6
"""

### FIXED CODE ###

import bisect
import sys
MAX_INT = int(10e12)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

def tami(index):
  if index == N:
    ans.append(-1)
    return
  num = a[index]
  if len(data[num]) == 1:
    ans.append(index)
    tami(index+1)
  elif index == data[num][-1]:
    ans.append(index)
    tami(data[num][0]+1)
  else:
    tmp = bisect.bisect_left(data[num],index)
    #print(num,data[num],tmp)
    tami(data[num][tmp+1]+1)

N,K = IL()
a = IL()

data = [[] for i in range(200010)]
ans = []

for i in range(N):
  data[a[i]].append(i)

#print(data)

tami(0)

#print(ans)
#print(len(ans),K)
#print(K%len(ans))

if K%len(ans) == 0:
  print()
else:
  x = ans[K%len(ans)-1]
  d = []
  d.append(a[x])
  while x != N-1:
    x += 1
    if len(data[a[x]]) == 1:
      d.append(a[x])
    elif x == data[a[x]][-1]:
      d.append(a[x])
    else:
      tmp = bisect.bisect_left(data[a[x]],x)
      x = data[a[x]][tmp+1]

  print(" ".join(map(str,d)))

"""
for i in range(K):
  for j in range(N):
    if a[j] in data:
      num = data.index(a[j])
      data = data[:num]
    else:
      data.append(a[j])
  print(data)

11 10
1 2 3 0 4 5 6 0 4 5 6

11 10
3 1 4 1 5 9 2 6 5 3 5

10 10
1 4 8 3 5 4 2 3 4 6
"""
N, K = map(int, input().split())
h = list(map(int, input().split()))
count=0
 
while i in range(N):
  if h[i] >= K:
    count+=1
 
print(count)

### FIXED CODE ###

N, K = map(int, input().split())
h = list(map(int, input().split()))
count=0
 
for i in range(N):
  if h[i] >= K:
    count+=1
 
print(count)
N,K = map(int,input().split())
tree_list = [int(input()) for _ in range(N)]
tree_list = sorted(tree_list)
ans = 10**9
for i in range(N-K+1):
    compare = tree_list[i+2]-tree_list[i]
    if ans > compare:
        ans = compare
print(ans)
    

### FIXED CODE ###

N,K = map(int,input().split())
tree_list = [int(input()) for _ in range(N)]
tree_list = sorted(tree_list)
ans = 10**9
for i in range(N-K+1):
    compare = tree_list[i+K-1]-tree_list[i]
    if ans > compare:
        ans = compare
print(ans)
nv,ne = [int(i) for i in input().split()]

g = []

for i in range(nv):
    g.append([])

for i in range(ne):
    s,t = [int(j) for j in input().split()]
    g[s].append(t)

done = []

f = 0

def put_forword(index):
    global f

    if index in done:
        return

    done.append(index)

    for s in g[index]:

        if s == 0:
            f = 1
            return
        put_forword(s)

put_forword(0)

print(f)



### FIXED CODE ###

import math

c1x,c1y,c1r = [int(i) for i in input().split()]
c2x,c2y,c2r = [int(i) for i in input().split()]

d = math.sqrt(pow(c1x-c2x, 2) +  pow(c1y-c2y, 2))

bcr = 0
scr = 0

if c1r > c2r:
    bcr = c1r
    scr = c2r
else:
    bcr = c2r
    scr = c1r


if d > bcr + scr:
    print(4)
elif d == bcr + scr:
    print(3)
elif d + scr > bcr:
    print(2)
elif d + scr == bcr:
    print(1)
else:
    print(0)
n = int(input)
ans = {}
for i in range(n):
    s = input()
    t = []
    for i in range(len(s)):
        t.append(s[i])
    t.sort()
    k = "".join(t)
    if k in ans:
        ans[k] = ans[k]+1
    else:
        ans[k] = 0
answer = 0
for i in ans:
    j = ans[i]
    answer += j*(j+1)//2
print(answer)

### FIXED CODE ###

N = int(input())
s = [0]*N
p = {}
ans = 0
for i in range(N):
    s[i] = "".join(sorted(input()))
    if s[i] in p:
        ans += p[s[i]]
        p[s[i]] += 1
    else:
        p[s[i]] = 1

print(ans)
while True:
    (m, f, r) = [int(i) for i in input().split()]
    if m == f == r == -1:
        break

    mf = m + f
    
    if m == -1 or == -1 of mf < 30:
        print('F')
    elif mf < 50 and r < 50:
        print('D')
    elif mf < 65:
        print('C')
    elif mf < 80:
        print('B')
    else:
        print('A')

### FIXED CODE ###

while True:
    m, f, r = map(int, input().strip().split())
    if m == f == r == -1: break

    if m == -1 or f == -1 or m + f < 30:
        print('F')
    elif m + f >= 80:
        print('A')
    elif m + f >= 65:
        print('B')
    elif m + f >= 50:
        print('C')
    elif m + f >= 30:
        print('C' if r >= 50 else 'D')
x = map(int(), input().split())
x.sort()
if x[0] == 5 and x[1] == 5 and x[2]== 5:
  print("YES")
else:
  print("NO")

### FIXED CODE ###

x = list(map(int, input().split()))
x.sort()
if x[0] == 5 and x[1] == 5 and x[2]== 7:
  print("YES")
else:
  print("NO")
import sys
from math import log, ceil, floor

fin = sys.stdin.readline
A, B = [int(elem) for elem in fin().split()]

# O(lg(max{A, B}))
result = 0
num_bits = floor(log(B, 2))
for d in range(num_bits + 1):
    base = 1 << d
    quo_A, rem_A = divmod(A, base << 1)
    quo_B, rem_B = divmod(B, base << 1)
    if quo_A != quo_B:
        parity = (base - max(0, rem_A - base) + max(0, rem_B - (base - 1))) % 2
    else:
        parity = 0 if rem_A < base and rem_B < base else \
            (rem_B - base + 1 - max(0, rem_A - base)) % 2
    if parity:
        result |= 1 << d

print(result)


### FIXED CODE ###

import sys
from math import log, ceil, floor

fin = sys.stdin.readline
A, B = [int(elem) for elem in fin().split()]

def partial_f(n):
    if n == 0:
        return 0
    return ((n + 1) >> 1) & 1 if n & 1 else n | ((n >> 1) & 1)


print(partial_f(A - 1) ^ partial_f(B))
a=int(input())
h=list(map(int,input().split()))
m=0
r=True
for i in h:
  m=max(m,i)
  if m!=i:
    r=i+1=<m
print("NYoe s"[r::2])


### FIXED CODE ###

input()
h=list(map(int,input().split()))
m=0
r=True
for i in h:
  r=i>=m-1
  if not(r):
    break
  m=max(m,i)
print("NYoe s"[r::2])
import math
from functools import reduce

def gcd_list(numbers):
    return reduce(math.gcd, numbers)

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

if len(a) == 2:
    answer = max(a)
else:
    for i in range(len(a)):
        val = a[i]
        a_filter = [k for k in a if str(k)!=str(val)]
        answer_b = gcd_list(a_filter)
        if answer_b > answer:
            answer = answer_b
print(answer)

### FIXED CODE ###

import fractions
n = int(input())
a = [0] + list(map(int,input().split())) + [0]


#はじめと最初の値を代入
L = [0] * (n+2)
R = [0] * (n+2)

for i in range(n):
    L[i+1] = fractions.gcd(L[i], a[i+1])

for j in range(n,0,-1):
    R[j] = fractions.gcd(R[j+1],a[j])

#print(a)
#print(L)
#print(R)

print(max(fractions.gcd(L[k-1],R[k+1]) for k in range(1,len(L)-1)))
a, b, c, d = map(int, raw_input().split())

print a, b, c, d

if a >= c:
    ans = b - c
else:
    ans = d - a

if ans < 0:
    print 0
else:
    print ans



### FIXED CODE ###

def func(s):
    key = len(s)
    for i in range(len(s)):
        if s[key - i - 1] != s[i]:
            return -1
    return 0

s = raw_input()

n = func(s)

if n == 0:
    print "Yes"
else:
    print "No"
s = input()
K = int(input())

sArr = list(s)
endpoint = len(sArr) - 1
result = ""

for i in range(len(sArr)):
    if ord("z") - ord(sArr[i]) + 1 <= K:
        K -= ord("z") - ord(sArr[i]) + 1
        sArr[i] = "a"

while K > 0:
    if ord("z") - ord(sArr[endpoint]) >= K:
        sArr[endpoint] = chr(ord(sArr[endpoint]) + K)
        K = 0
    else:
        sArr[endpoint] = "z"
        K -= ord("z") - ord(sArr[endpoint])
        endpoint -= 1
    if endpoint == 0 and K != 0:
        while endpoint != len(s) - 1:
            sArr[endpoint] = "a"
            K -= 1
            endpoint += 1

for j in range(len(sArr)):
    result += sArr[j]

print(result)

### FIXED CODE ###

s = input()
K = int(input())

sArr = list(s)
endpoint = len(sArr) - 1
result = ""

for i in range(len(sArr)):
    if K == 0:
        break
    else:
        if (123 - ord(sArr[i])) <= K:
            K -= (123 - ord(sArr[i])) % 26
            sArr[i] = "a"

if K > 0:
    K %= 26
    sArr[endpoint] = chr(ord(sArr[endpoint]) + K)

for j in range(len(sArr)):
    result += sArr[j]

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

answer = 1
if 0 in A:
    print(0)
else:
    for i in A:
        answer *= i
        if answer > 10**18:
            print(-1)
            exit()
    print(answer)
    

### FIXED CODE ###

a = list(map(int, input().split()))
print(a[0] * a[1])
n,m,r=map(int,input().split())
r=list(map(int,input().split()))
cost=[[99999999 if i!=j else 0 for j in range(n)] for i in range(n)]
for _ in range(m):
    a,b,c=map(int,input().split())
    cost[a-1][b-1]=cost[b-1][a-1]=c
for k in range(n):
    for i in range(n):
        for j in range(n):
            cost[i][j]=min(cost[i][j],cost[i][k]+cost[k][j])
c=[[cost[y-1][x-1] for x in r] for y in r]
print(max(map(max,c)))

### FIXED CODE ###

a=int(input())
print("Yes") if a//10==9 or a%10==9 else print("No")
n = int(input())
*w,=open(0).read().split()
for i in range(1,n):
  if w.count(w[i]) == 1 and w[i-1][-1] == w[i][0]:
    pass
  else:
    print('No')
    break
  if i == n-1:
    print('Yes')
  else:
    pass

### FIXED CODE ###

n = int(input())
w=[]
for i in range(n):
    w.append(input())
a=0
for i in range(1,n):
    if w.count(w[i])==1 and w[i-1][-1]==w[i][0]:
       a += 1
    else:
        print('No')
        break
    if a==n-1:
        print('Yes')
    else:
        pass
S = input()
m = 1
num = 1
for c in S:
  if c == '<':
    num += 1
  elif c == '>':
    num -= 1
  m = min(num, m)
if m <= 0:
  num += 1 - m
else:
  num = 1
ans += num
for c in S:
  if c == '<':
    num += 1
  elif c == '>':
    num -= 1
  ans += num
print(ans)

### FIXED CODE ###

S = input()
INC = '<'
DEC = '>'
icnt = 0
dcnt = 0
mode = DEC
ans = 0
for c in S:
  if mode == DEC:
    if c == DEC:
      dcnt += 1
    elif c == INC:
      if icnt <= dcnt:
        ans += (dcnt + 1) * dcnt // 2
      else:
        ans += icnt + dcnt * (dcnt - 1) // 2
      icnt = 1
      mode = INC
  elif mode == INC:
    if c == INC:
      icnt += 1
    elif c == DEC:
      ans += icnt * (icnt - 1) // 2
      dcnt = 1
      mode = DEC
if mode == INC:
  ans += (icnt + 1) * icnt // 2
elif mode == DEC:
  if icnt <= dcnt:
    ans += (dcnt + 1) * dcnt // 2
  else:
    ans += icnt + dcnt * (dcnt - 1) // 2
print(ans)
import math
n=int(input())
arr=list(map(int,input().split()))
dic={}
for c in arr:
    dic.setdefault(c,0)
    dic[c]+=1
ans=True
#n is odd 5(4 2 0 2 4)
if n%2!=0:
    for c in range(0,n-1,2):
        if c==0 and dic[c]!=1:
            ans=False
        if dic[c]!=2:
            ans=False
            break
#n is even 8 (7 5 1 1 7 3 5 3)        
else:
    for c in range(1,n-1,2):
        if dic[c]!=2:
            ans=False
if ans and n!=0:
    print(2**math.floor(n/2)%((10**9)+7))
else:
    print(0)
  

### FIXED CODE ###

N=int(input())
l=list(map(int,input().split()))
a=1
if N%2==0:
    if len(l)!=len(set(l))*2:
        a=0
else:
    if l.count(0) == 1:
        l.remove(0)
        if len(l) != 2*len(set(l)):
            a = 0
    else:
        a=0
if a:
      print((2**(N//2))%(10**9+7))
else:
      print(0)
n, k = map(int,input().split())
a_list = list(map(int,input().split()))
a_list.sort()

from operator import mul
from functools import reduce

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

sum_val = 0
val = cmb(n-1, k-1)
for i in range(n-k+1):
    if i != 0:
        val = val*(n-i-k+1)/(n-i)
    sum_val = (sum_val + (a_list[-(i+1)]*val)%(10**9+7) - (a_list[i]*val)%(10**9+7))%(10**9+7)

print(int(sum_val))

### FIXED CODE ###

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


mod = 10 ** 9 + 7
f_list = [1]
for i in range(1,n+1):
    f_list.append((f_list[-1] * i) % mod)
def comb(n,r):
    return f_list[n] * (pow(f_list[r], mod-2, mod) * pow(f_list[n-r], mod-2, mod) % mod) % mod


max_val = 0
min_val = 0
for i in range(n - k + 1):
    val = comb(n - i - 1, k - 1)
    max_val = (max_val + (((a_list[-(i + 1)]) * val))) % (10 ** 9 + 7)
    min_val = (min_val + ((a_list[i]) * val)) % (10 ** 9 + 7)

print(int((max_val - min_val) % (10 ** 9 + 7)))
N = input()
S = input()
T = input()
 
Q = ""
for i in range (N):
  Q = Q + S[i] + T[i]
  
print(Q)

### FIXED CODE ###

N = int(input())
S,T = input().split()
 
Q = ""
for i in range (N):
  Q = Q + S[i] + T[i]
  
print(Q)
H, W = map(int, input().split())
a = []

for i in range(H):
    a.append([int(x) for x in input().split()])

n = 0
ans = []
for y in range(H):
    if y % 2 == 0:
        for x in range(W - 1):
            if a[y][x] & 1:
                a[y][x + 1] += 1
                n += 1
                ans.append("{} {} {} {}".format(y + 1, x + 1, y + 1, x + 2))
        if y != H - 1 and a[y][W - 1] & 1:
            a[y + 1][W - 1] += 1
            n += 1
            ans.append("{} {} {} {}".format(y + 1, W, y + 2, x + W))

    else:
        for x in range(W - 1, 0, -1):
            if a[y][x] & 1:
                a[y][x - 1] += 1
                n += 1
                ans.append("{} {} {} {}".format(y + 1, x + 1, y + 1, x))
        if y != H - 1 and a[y][0] & 1:
            a[y + 1][0] += 1
            n += 1
            ans.append("{} {} {} {}".format(y + 1, x + 1, y + 2, x + 1))

print(n)
print("\n".join(ans))

### FIXED CODE ###

def main():
    ans, a = [], []
    H, W = map(int, input().split())

    for i in range(H):
        a += [list(map(int, input().split()))]

    x, y, dx = 0, 0, 1

    while True:
        nx, ny = x, y
        if x+dx < 0 or W <= x+dx:
            nx = x
            ny = y+1 
            dx *= -1
        else:
            nx = x+dx
            ny = y

        if H <= ny:
            break

        if a[y][x] % 2 == 1:
            a[y][x] -= 1
            a[ny][nx] += 1
            ans += [str(y+1) + " " + str(x+1) + " " + str(ny+1) + " " + str(nx+1)]
        x, y = nx, ny

    print (len(ans))

    for i in ans:
        print (i)

main()
N, K = map(int, input().split())
l = list(map(int, input().split()))

l = sorted(l. reverse = True)

print(sum(l[:K]))

### FIXED CODE ###

N, K = map(int, input().split())
l = list(map(int, input().split()))

l = sorted(l, reverse = True)

print(sum(l[:K]))
from itertools import accumulate
import numpy as np

n, k = map(int, input().split())
p = np.array(list(map(int, input().split())), dtype=np.int64)

p = (1 + p) / 2
p = [0] + list(accumulate(p))
ans = 0
for i in range(k):
    ans = max(ans, p[i + k] - p[i])
print(ans)

### FIXED CODE ###

from itertools import accumulate
import numpy as np

n, k = map(int, input().split())
p = np.array(list(map(int, input().split())), dtype=np.int64)

p = (1 + p) / 2
p = [0] + list(accumulate(p))
ans = 0
for i in range(n - k + 1):
    ans = max(ans, p[i + k] - p[i])
print(ans)
import sys
sys.setrecursionlimit(10**7)
H, W = map(int, input().split())
g = [input() for _ in range(H)]
white = 0
black = 0
for i in range(H):
    for j in range(W):
        if g[i][j] == '#':
            black += 1
        else:
            white += 1
[[0]*W for _ in range(H)]
dist = 10**9
def dfs(x, y,visit, n):
    if x < 0 or x >= H or y < 0 or y >= W or g[x][y] == '#':
        return 0
    elif x == H-1and y == W-1:
        global dist
        if n < dist:
            dist = n
        return 0
    elif visit[x][y]:
        return 0
    else:
        visit[x][y] = 1
        dfs(x+1, y, n+1)
        dfs(x, y+1, n+1)
        dfs(x-1, y, n+1)
        dfs(x, y-1, n+1)
dfs(0, 0,[[0]*W for _ in range(H)] ,1)
if dist == 10**9:
    print(-1)
else:
    print(white - dist)

### FIXED CODE ###

H, W = map(int, input().split())
g = [input() for _ in range(H)]
white = 0
black = 0
for i in range(H):
    for j in range(W):
        if g[i][j] == '#':
            black += 1
        else:
            white += 1
start = (0, 0)
goal = (H-1, W-1)
S = [start]
T = {start: 1}
while S and goal not in T:
    S2 = []
    for x, y in S:
        for pos in [(x+1, y), (x-1, y), (x, y+1), (x, y-1)]:
            x2, y2 = pos
            if 0<= x2 <= H-1 and 0<= y2 <= W-1:
                if g[x2][y2] != '#' and pos not in T:
                    T[pos] = T[(x, y)] + 1
                    S2.append(pos)
    S = S2
if goal not in T:
    print(-1)
else:
    print(white - T[goal])
NM = input()
N = int(NM.split(' ')[0])
M = int(NM.split(' ')[1])
each_days_map = {}
max_sort_list = [0]

def insert_max_sort(b):
    for idx in range(len(max_sort_list)):
        if b > max_sort_list[idx]:
            max_sort_list.insert(idx,b)
            if len(max_sort_list) > M:
                max_sort_list.pop()
            break

for i in range(N):
    ab = input()
    a = int(ab.split(' ')[0])
    b = int(ab.split(' ')[1])
    if a > M or b < max_sort_list[len(max_sort_list)-1]:
        continue
    if a in each_days_map.keys():
        a_len = len(each_days_map[a])
        if b > each_days_map[a][a_len-1]:
            for idx in range(a_len):
                if b > each_days_map[a][idx]:
                    each_days_map[a].insert(idx,b)
                    if a_len > (M - a + 1):
                        removed_num = each_days_map[a][a_len-1]
                        each_days_map[a].pop()
                        max_sort_list.remove(removed_num)
                    insert_max_sort(b)
                    break
        else:
            if M > a_len and (M - a + 1) > a_len:
                each_days_map[a].append(b)
                insert_max_sort(b)
    else:
        each_days_map[a] = [b]
        insert_max_sort(b)
print(sum(max_sort_list))

### FIXED CODE ###

import heapq
NM = input()
N = int(NM.split(' ')[0])
M = int(NM.split(' ')[1])
each_days_list = [[] for _ in range(M)]
 
for i in range(N):
    ab = input()
    a = int(ab.split(' ')[0])
    b = int(ab.split(' ')[1])
    if a <= M:
        each_days_list[a-1].append(b)

max_list = []
salary_count = 0
for i in range(M):
    for j in range(len(each_days_list[i])): 
        heapq.heappush(max_list,-each_days_list[i][j])
    if len(max_list) > 0:
        salary_count += -heapq.heappop(max_list)
        
print(salary_count)
a, b = map(int, input().split())
 
ans = max([a - 2*b, 0])
 
	
for num in range(100000000):

print(ans)

### FIXED CODE ###

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

ans = max([a - 2*b, 0])

print(ans)
s = input()
s = list(s)
s2 = input()
s2 = list(s2)
count=1
X = int(s[2])
count = 1
for i in s2:
    if i == ' ':
        continue
    X = X-int(i)
    if X < 0:
        break
    count += 1
print(count)



### FIXED CODE ###

s = input().split()
s = list(s)
s2 = input().split()
s2 = list(s2)
count=1
X = int(s[1])
count = 1
for i in s2:
    if i == ' ':
        continue
    X = X-int(i)
    if X < 0:
        break
    count += 1
print(count)
#最大公約数
def gcd(a,b):
    while b!=0:
        a,b = b, a%b
    return a

#最小公倍数
def lcm(a,b):
    return a*b //gcd(a,b)

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

l = lcm(n,m)
txt = ['.']*l

res = l
for i in range(n):
    txt[i*(l//n)] = s[i]
for i in range(m):
    if txt[i*(l//m)]=='.' or txt[i*(l//m)]==t[i]:
        continue
    else:
        res = -1
print(res)

### FIXED CODE ###

def gcd(a, b):
	while b:
		a, b = b, a % b
	return a
def lcm(a, b):
	return a * b // gcd (a, b)
 
n,m = map(int,input().split())
s = input()
t = input()

l = lcm(n,m)
gaps = l//m
gapt = l//n

i,j = 0,0
while i<n:
    if s[i]!=t[j]:
        print(-1)
        break
    else:
        i += gaps
        j += gapt
else:
    print(l)
import sys
sys.setrecursionlimit(100000)

def neighbor(N, edges):
    neighbor_list = [[] for _ in range(N)]
    for i in range(N):
        for vs in edges:
            if i + 1 in vs: # vsは頂点i+1が含まれるedge
                neighbor_list[i] += vs
        neighbor_list[i] = list(set(neighbor_list[i]))
        neighbor_list[i].remove(i + 1)
        
    return neighbor_list

def neighbor2(N, edges):
    nlist = neighbor(N, edges)
    nneighbor_list = [[] for _ in range(N)]
    for i in range(N):
        nneighbor_list[i] += nlist[i]
        for e in nlist[i]:
            nneighbor_list[i] += nlist[e - 1]
        nneighbor_list[i] = list(set(nneighbor_list[i]))
        nneighbor_list[i].remove(i + 1)
    return nneighbor_list
        
        
def combination(N, K, nnlist):
    combi = 1
    clist = [False]*N
    for v in range(N):
        print(combi)
        combi *= (K - len([t for t in nnlist[v] if clist[t-1]]))
        clist[v] = True
    return combi

def paint(N, K, nlist, nnlist, clist, vlist, combi):
    for v in vlist:
        #nnlistの中で塗られている頂点の数を数え、色候補数Kから引く
        combi *= (K - len([t for t in nnlist[v - 1] if clist[t-1]])) 
        clist[v - 1] = True #頂点vを塗る
        vlist_next = [t for t in nlist[v - 1] if not clist[t-1]]
        if len(vlist_next) != 0:
            combi = paint(N, K, nlist, nnlist, clist, vlist_next, combi)
    return combi


if __name__ == '__main__':
    N, K = map(int, input().split())
    edges = [None]*(N-1)
    
    for i in range(N-1):
        edges[i] = list(map(int, input().split()))
    
    nlist = neighbor(N, edges)
    nnlist = neighbor2(N, edges)
    print(paint(N, K, nlist, nnlist, clist=[False]*N, vlist=[1], combi=1)%1000000007)

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)

def neighbor(N, edges):
    neighbor_list = [[] for _ in range(N)]
    for a, b in edges:
        neighbor_list[a-1] += [b-1]
        neighbor_list[b-1] += [a-1]
        
    return neighbor_list


def paint(K, nlist, now_num, from_num, case_num):
        mod = 1000000007
        if  from_num == -1:
            can_use_color = K - 1
        else:
            can_use_color = K - 2
        
        if len(nlist[now_num]) - 1 > can_use_color:
            return 0
        
        for child in nlist[now_num]:
            if child == from_num:
                continue
            else:
                case_num *= can_use_color
                can_use_color -= 1
                case_num %= mod
        
        for child in nlist[now_num]:
            if child == from_num:
                continue
            else:
                case_num = paint(K, nlist, child, now_num, case_num)
        return case_num%mod
            

if __name__ == '__main__':
    N, K = map(int, input().split())
    edges = [None]*(N-1)
    
    for i in range(N-1):
        edges[i] = list(map(int, input().split()))
    
    nlist = neighbor(N, edges)


    print(paint(K, nlist, 0, -1, K))