Harryxun/stf_run huggingface dataset:
from itertools import accumulate
n, k = map(int, input().split())
s = input()

compressed = []

first = s[0]
prev = s[0]
cnt = 1
for x in s[1:]:
    if prev == x:
        cnt += 1
    else:
        if x == "1":
            compressed.append(cnt)
            cnt = 1
        else:
            compressed.append(cnt)
            cnt = 1
    prev = x
compressed.append(cnt)


result = [0] + list(accumulate(compressed))

ans = []
if first == "1":
    for i in range(0, (len(s) - 2 * k) // 2, 2):
        ans.append(result[i + 2 * k + 1] - result[i])
    for i in range(1, (len(s) - 2 * k) // 2, 2):
        ans.append(result[i + 2 * k] - result[i])
else:
    for i in range(0, (len(s) - 2 * k) // 2, 2):
        ans.append(result[i + 2 * k] - result[i])
    for i in range(1, (len(s) - 2 * k) // 2, 2):
        ans.append(result[i + 2 * k + 1] - result[i])

print(max(ans))

### FIXED CODE ###

from itertools import accumulate
n, k = map(int, input().split())
s = input() + "_"

compressed = []

first = s[0]
prev = s[0]
cnt = 1
for x in s[1:]:
    if prev == x:
        cnt += 1
    else:
        if x == "1":
            compressed.append(cnt)
            cnt = 1
        else:
            compressed.append(cnt)
            cnt = 1
    prev = x


result = [0] + list(accumulate(compressed))

ans = []
if first == "1":
    for i in range(0, len(result), 2):
        ans.append(result[min(i + k * 2 + 1, len(result) - 1)] - result[i])
    for j in range(1, len(result), 2):
        ans.append(result[min(j + k * 2, len(result) - 1)] - result[j])
else:
    for i in range(0, len(result), 2):
        ans.append(result[min(i + k * 2, len(result) - 1)] - result[i])
    for j in range(1, len(result), 2):
        ans.append(result[min(j + k * 2 + 1, len(result) - 1)] - result[j])

print(max(ans))
from collections import defaultdict,deque
H, W = map(int,input().split())
MAP = []
for _ in range(H):
    MAP.append(tuple(map(str,input())))

move = [[0,1],[0,-1],[1,0],[-1,0]]

def bfs(s):
    MAX = 0
    stack = deque([])
    stack.append(tuple(s))
    depth =dict()
    depth[tuple(s)] = 0
    goal = s
    while stack:
        v = stack.popleft()
        for m in move:
            a = tuple([v[0]+m[0], v[1] + m[1]])
            if a[0] < H and a[0] >=  0 and a[1] < W and a[1] >= 0:
                if MAP[a[0]][a[1]] == '.' and not a in depth:
                    stack.append(a)
                    depth[a] = depth[v] + 1

    for k,d in depth.items():
        if MAX < d:
            MAX = d
            goal = k

    return MAX, goal


for i in range(0,H):
    for r in range(0,W):
        if "." in MAP[r]:
            start = [r, MAP[r].index(".")]
MAX, goal = bfs(tuple(start))
MAX, _ = bfs(tuple(goal))
print(MAX)
exit()



### FIXED CODE ###

from collections import defaultdict,deque
H, W = map(int,input().split())
MAP = []
for _ in range(H):
    MAP.append(tuple(map(str,input())))

move = [[0,1],[0,-1],[1,0],[-1,0]]
MAX = 0 

def bfs(s):
    global MAX
    stack = deque([])
    stack.append(tuple(s))
    depth =dict()
    depth[tuple(s)] = 0
    while stack:
        v = stack.popleft()
        for m in move:
            a = tuple([v[0]+m[0], v[1] + m[1]])
            if a[0] < H and a[0] >=  0 and a[1] < W and a[1] >= 0:
                if MAP[a[0]][a[1]] == '.' and not a in depth:
                    stack.append(a)
                    depth[a] = depth[v] + 1

    for d in depth.values():
        MAX = max(MAX,d)


for i in range(0,H):
    for j in range(0,W):
        if MAP[i][j] == '.':
            bfs(tuple([i,j]))

for i in range(0,W):
    for j in range(0,H):
        if MAP[j][i] == '.':
            bfs(tuple([j,i]))

print(MAX)
S = 'ABC'
if S = 'ABC':
print('ARC')
else:
print('ABC')

### FIXED CODE ###

s=input()
print("ABC" if s=="ARC" else "ARC")
a, b, c = map(int, input().spulit())
 
if a <= b * c:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

d,t,s=map(int,input().split())
if d<=t*s:
    print("Yes")
else:
    print("No")
import numpy as np
N = int(input())
A = np.array(input().split(), dtype = np.int32)

counter = np.bincount(A)
answer = (counter[2:] + counter[1:-1] + counter[:-2]).max()
print(answer)

### FIXED CODE ###

import numpy as np
# 前後1まで回収できる
N = int(input())

# n以下のものをかぞえる
A = np.bincount(np.array(input().split(), dtype=np.int32))

B = A.copy() # そのままとる
B[1:] += A[:-1] # 1増やして回収
B[:-1] += A[1:] # 1減らして回収

answer = B.max()
print(answer)
A , B , C , D = map(int,input().split())

if C == 1 and D != 1 :
  print(0)
elif D == 1 and C != 1 :
  print(1)
else :
  print(z)

### FIXED CODE ###

import math
import fractions

# A以上B以下の数でXの倍数の個数
def countX(X) :
    if X > B :
        return 0

    minX = (A - 1) // X
    maxX = B // X

    return maxX - minX

A , B , C , D = map(int,input().split())

ans = B - A + 1

# 最小公倍数
Z = int(C * D / fractions.gcd(C,D))

ans -= countX(C)
ans -= countX(D)
ans += countX(Z)

print(int(ans))
n, k = map(int, input().split())
p = list(map(int, input().split()))
e = []
m = 0
arr = []
ans = 0
for i in range(n):
  m += (p[i] + 1) / 2
  e.append(m)
for i in range(n - k):
  arr.append(e[i + k] - e[i])
ans = max(arr)
print(ans)

### FIXED CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))
e = []
m = 0
arr = []
ans = 0
for i in range(n):
  m += (p[i] + 1) / 2
  e.append(m)
arr.append(e[k - 1])
for i in range(n - k):
  arr.append(e[i + k] - e[i])
ans = max(arr)
print(ans)
n,k = map(int,input().split())

s = list(map(int,input()))

ans = 0

x = []

f = s[0]

z = 0
o = 0
ans = 0

for i in s:
    if i == 0:
        if f == 1:
            x.append(o)
            o = 0
            z += 1
            f = 0
        else:
            z += 1
    else:
        if f == 0:
            x.append(z)
            z = 0
            o += 1
            f = 1
        else:
            o += 1
    
if s[-1] != s[-2]:
    x.append(1)
else:
    x[-1] += 1
    
    
    
if k > len(x):
    print(sum(x))
else:
    for i in range(len(x)-k):
        ans = max(ans,sum(x[i:i+k+1]))
    print(ans)
    

### FIXED CODE ###

n,k = map(int,input().split())
s = list(map(int,list(input())))
x = [-1]
for i in range(n-1):
    if s[i] != s[i+1]:
        x.append(i)
x.append(n-1)
t = len(x)
ans = 1

for i in range(t-1):
    if i%2 == s[0]:
        ans = max(ans,x[min(t-1,i+2*k)]-x[i])
    else:
        ans = max(ans,x[min(t-1,i+2*k+1)]-x[i])

print(ans)
n=input()
a=list(map(int,input().split()))
h = a[0]
count = 0
for i in len(a):
    if h <= a[i]:
        count =+ 1
print(count)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
h = a[0]
count = 0
for i in range(n):
    if h <= a[i]:
        h = a[i]
        count = count + 1
print(count)
n,k = map(int, input().split())
a = list(map(int, input().split()))
 
ind = a.index(1)
 
left = ind
right = n-1-ind
import math
if left<k-1 or right<k-1:
	print (n//(k-1))
else:
	if k>=n:
		print (1)
	else:
		print(int(math.ceil(left/(k-1))+math.ceil(right/(k-1))))


### FIXED CODE ###

s = list(input())
print (s.count('+')-s.count('-'))
def main(): # A162
    N = int(input())
    NUM = list(str(N))
    NUM = list(map(int,NUM))
    #A = list(map(int, input().split()))  # [1,2,3,4,5]
    for i in NUM:
        if int(i) == 7:
            print("Yes")
            exit(1)
    print("No")
    
main()

### FIXED CODE ###

def main(): # A162
    N = int(input())
    NUM = list(str(N))
    NUM = list(map(int,NUM))
    #A = list(map(int, input().split()))  # [1,2,3,4,5]
    for i in NUM:
        if int(i) == 7:
            print("Yes")
            exit(0)
    print("No")
    
main()
N = int(input())  #スペース抜きの複数行,１文字ずつ
 
A = []
for i in range(1,N):
#    print(i)
    if i % 3 == 0:
        A.append(0)
    elif i % 5 == 0:
		A.append(0)
    else:
        A.append(i)
 
print(sum(A))

### FIXED CODE ###

n = int(input())  #スペース抜きの複数行,１文字ずつ
A = []

for i in range(1, n + 1):
    if i % 15 == 0:
        A.append(0)
    elif i % 3 == 0:
        A.append(0)
    elif i % 5 == 0:
        A.append(0)
    else:
        A.append(i)

print(sum(A))
import numpy as np
X = int(input())

t = np.arange(-600000, 600000, 1)
t = t**5
S = set(t)

for B in range(-600000, 600001, 1):
    if X+B**5 in S:
        print("%d %d"%((X+B**5)**0.2, B))
        break


### FIXED CODE ###

import numpy as np
X = int(input())

t = np.arange(0, 2000001, 1)
t = t**5
S = set(t)

for B in range(0,200001,1):
    if X+B**5 in S:
        print("%d %d"%((X+B**5)**0.2, B))
        break
    if X-B**5 in S:
        print("%d %d"%((X-B**5)**0.2, -B))
        break
y,m,d=map(int,input().split('/'))
if y < 2020 and m < 05:
    print('Heisei')
else:
    print('TBD')

### FIXED CODE ###


y,m,d=map(int,input().split('/'))
if y < 2020 and m < 5:
    print('Heisei')
else:
    print('TBD')
max = 0
cnt = 0
N = int(input())
for _ in range(N):
	p = int(input())
	if max < p
		max = p
		cnt += 1
print(cnt)

### FIXED CODE ###

min = 10000000
cnt = 0
N = int(input())
P = list(map(int, input().split()))

for i in range(N):
	p = P[i]
	if min >= p:
		min = p
		cnt += 1
print(cnt)
import collections
from scipy.special import comb

N = int(input())
s = []
for _ in range(N):
    s.append(list(input()))

for i in range(len(s)):
    s[i] = tuple(sorted(s[i]))
    
c = collections.Counter(s)

cnt = 0
for c_ in c.values():
    cnt += comb(c_, 2)
    
print(int(cnt))

### FIXED CODE ###

import collections
from scipy.misc import comb

N = int(input())
s = []
for _ in range(N):
    s.append(list(input()))

for i in range(len(s)):
    s[i] = tuple(sorted(s[i]))
    
c = collections.Counter(s)

cnt = 0
for c_ in c.values():
    cnt += comb(c_, 2, exact=True)
    
print(cnt)
N = int(input())
A = list(map(int, input().split()))
A_set = set(A)
if len(A_set) == N:
        print("YES")
    else:
        print("NO")

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
A_set = set(A)
if len(A_set) == N:
    print("YES")
else:
    print("NO")
n = int(input())
dot = {}
dotset = set()
for i in range(n):
    x, y = map(int, input().split())
    dot[i] = (x, y)
    dotset.add((x, y))

v = set()

cnt = 0
for i, f in dot:
    a, b = f
    for j, g in dot:
        if i == j: continue
        c, d = g
        if a == c or b == d: continue
        f1 = (a, d) in dotset
        f2 = (c, b) in dotset
        if f1 and not f2:
            cnt += 1
            dotset.add((c, b))
        if not f1 and f2:
            cnt += 1
            dotset.add((a, d))
print(cnt)

### FIXED CODE ###

from collections import defaultdict
n = int(input())
dx = defaultdict(list)
dy = defaultdict(list)
pts = set()
for _ in range(n):
    x, y = map(int, input().split())
    dx[x].append(y)
    dy[y].append(x)
    pts.add((x, y))

vx, vy = set(), set()
cnt = 0
for x, y in pts:
    if x in vx or y in vy: continue
    sx, sy = [x], [y]
    xs, ys = set(), set()
    while sx or sy:
        while sx:
            x = sx.pop()
            if x not in xs:
                xs.add(x)
                for y in dx[x]:
                    if y not in ys:
                        sy.append(y)
        while sy:
            y = sy.pop()
            if y not in ys:
                ys.add(y)
                for x in dy[y]:
                    if x not in xs:
                        sx.append(x)
    vx.update(xs)
    vy.update(ys)
    cnt += len(xs) * len(ys)
print(cnt - len(pts))
#!/usr/bin/env python3

import random
import numpy as np


N, M = [int(x) for x in input().split()]


def try_get(N: int, M: int) -> (bool, list):
    used_flag = np.zeros(N)
    stage_marks = []  # [(v1,v2)]
    ones = np.ones(N)
    for length in reversed(range(1, M+1)):
        numbers = np.arange(N - length) + 1
        numbers = numbers[np.logical_and(used_flag[:(N-length)]==0,used_flag[length:N]==0)]
        if len(numbers) == 0:
            return False, []
        num = np.random.choice(numbers)
        stage_marks.append((num, num + length))
        used_flag[num-1] = 1
        used_flag[num+length-1] = 1

    return True, stage_marks


ok = False
marks = []
while not ok:
    ok, marks = try_get(N, M)

for src, dst in marks:
    print("{} {}".format(src, dst))


### FIXED CODE ###


K = int(input())
A, B = [int(x) for x in input().split()]

print("OK" if A // K < B // K or A % K == 0 or B % K == 0 else "NG")
import sys

sys.setrecursionlimit(2*10**5)
input = sys.stdin.readline

n, q = map(int, input().split())
graph = {i: [] for i in range(n)}
for _ in range(n-1):
    a, b = map(lambda x: int(x)-1, input().split())
    graph[a].append(b)
    graph[b].append(a)
ans = [0] * n
for _ in range(q):
    p, x = map(int, input().split())
    ans[p-1] += x

def dfs(now, parent):
    if parent != -1:
        ans[now] += ans[parent]
    for i in graph[now]:
        if i != parent:
            dfs(i, now)

dfs(0, -1)
print(' '.join(map(str, ans)))


### FIXED CODE ###

import sys

sys.setrecursionlimit(10**7)
input = sys.stdin.readline

n, q = map(int, input().split())
graph = {i: [] for i in range(n)}
for a, b in [[int(i)-1 for i in input().split()] for _ in range(n-1)]:
    graph[a].append(b)
    graph[b].append(a)
ans = [0] * n
for p, x in [[int(i) for i in input().split()] for _ in range(q)]:
    ans[p-1] += x

def dfs(now, parent):
    if parent != -1:
        ans[now] += ans[parent]
    for i in graph[now]:
        if i == parent:
            continue
        dfs(i, now)

dfs(0, -1)
print(' '.join(map(str, ans)))
s=inpput()
if(s="ABC"):
    print("ARC")
else:
    print("ABC")

### FIXED CODE ###

s=input()
if(s=="ABC"):
    print("ARC")
else:
    print("ABC")
k,n=int(input().split())
a = list(map(int,input().split()))
m = int(0)

for i in range(n-1)
	m = max(m,a[i+1]-m[n])

x = k-m
print(x)

### FIXED CODE ###

k,n=map(int,input().split())
a = list(map(int,input().split()))
m = k-a[n-1]+a[0]
for i in range(n-1):
	m = max(m,a[i+1]-a[i])
x = k-m
print(x)
h, w = map(int, input().split())
inf = float('INF')
A = []
B = []

for i in range(h):
    line = list(map(int, input().split()))
    A.append(line)

for i in range(h):
    line = list(map(int, input().split()))
    B.append(line)

D = [[0]*w for i in range(h)]
for i in range(h):
    for j in range(w):
        D[i][j] = abs(A[i][j] - B[i][j])


def slide_down(y, x, possible: set):
    new = set()
    delta = D[y+1][x]
    for num in possible:
        if num + delta <=6400:
            new.add(num+delta)
        if abs(num-delta) <= 6400:
            new.add(abs(num-delta))
    return new


def slide_right(y, x, possible: set):
    new = set()
    delta = D[y][x+1]
    for num in possible:
        if num + delta <=6400:
            new.add(num+delta)
        if abs(num-delta) <=6400:
            new.add(abs(num-delta))
    return new


DP = [[set() for j in range(w)] for i in range(h)]
DP[0][0] = {D[0][0]}
for row in range(h):
    for col in range(w):
        possible = DP[row][col]
        if col < w-1:
            new = slide_right(row, col, possible)
            DP[row][col+1] |= new
        if row < h-1:
            new = slide_down(row, col, possible)
            DP[row+1][col] |= new

ans = min(DP[h-1][w-1])
print(ans)


### FIXED CODE ###

A = list(map(int, input().split()))
if sum(A) >= 22:
    print('bust')
else:
    print('win')
N = int(input())
XY = [list(map(int, input().split())) for _ in range(N)]

from itertools import permutations
from collections import Counter
l = [((A[0]-B[0]),(A[1]-B[1])) for A,B in permutations(XY,2)]
c = Counter(l)
print(N - c.most_common()[0][1] )

### FIXED CODE ###

N = int(input())
XY = [list(map(int, input().split())) for _ in range(N)]

if N==1:
  print(1)
  exit()

from itertools import permutations
from collections import Counter
l = [((A[0]-B[0]),(A[1]-B[1])) for A,B in permutations(XY,2)]
c = Counter(l)
print(N - c.most_common()[0][1] )
from string import ascii_lowercase as letters

data = ''
while True:
	temp = input()
	if temp == '':
		break
	else:
		data += temp.lower()

num = [data.count(s) for s in letters]
ans = '\n'.join(['{0} : {1}'.format(s,n) for s,n in zip(list(letters),num)])
print(ans)

### FIXED CODE ###

from string import ascii_lowercase as letters
import sys
data = sys.stdin.read().lower()

num = [data.count(s) for s in letters]
ans = '\n'.join(['{0} : {1}'.format(s,n) for s,n in zip(list(letters),num)])
print(ans)
n=int(input())
for i in range(n):
    t,x,y=map(int,input().split())
    if x+Y>t or (x+y+t)%2==1:
      print("NO")
      exit()
print("YES")


### FIXED CODE ###

a,b=map(int,input().split())
print("Even" if a*b%2==0 else "Odd")
A, B, C, K = map(int, input().split())

if (A+B) == K:
  print(A)
elif (A+B) > K:
  if a > K:
    print(K)
  else:
    print(A)
elif (A+B) < K:
  print(A - (K - (A+B)))


### FIXED CODE ###

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

if (A+B) == K:
  print(A)
elif (A+B) > K:
  if A > K:
    print(K)
  else:
    print(A)
elif (A+B) < K:
  print(A - (K - (A+B)))
# -*- coding: utf-8 -*-
 
## Library
 
import sys
from fractions import gcd
import math
from math import ceil,floor
import collections
from collections import Counter
import itertools
import copy
 
## input
 
# N=int(input())
# A,B,C,D=map(int, input().split())
# S = input()
# yoko = list(map(int, input().split()))
# tate = [int(input()) for _ in range(N)]
# N, M = map(int,input().split()) 
#    P = [list(map(int,input().split())) for i in range(M)]
#    S = []
#    for _ in range(N):
#        S.append(list(input()))
 
N,M = map(int, input().split())
X = list(map(int, input().split()))

X.sort()

ans = X[M-1] - X[0]
tmp = []

for i in range(1,M):
    tmp2 = X[i] - X[i-1]
    if len(tmp) < N-1:
        tmp.append(tmp2)
    else:
        tmp3 = min(tmp)
        if tmp3 < tmp2:
            tmp.remove(tmp3)
            tmp.append(tmp2)

print(ans - sum(tmp))

### FIXED CODE ###

# -*- coding: utf-8 -*-
 
## Library
 
import sys
from fractions import gcd
import math
from math import ceil,floor
import collections
from collections import Counter
import itertools
import copy
 
## input
 
# N=int(input())
# A,B,C,D=map(int, input().split())
# S = input()
# yoko = list(map(int, input().split()))
# tate = [int(input()) for _ in range(N)]
# N, M = map(int,input().split()) 
#    P = [list(map(int,input().split())) for i in range(M)]
#    S = []
#    for _ in range(N):
#        S.append(list(input()))
 
N,M = map(int, input().split())
X = list(map(int, input().split()))


X.sort()

ans = X[M-1] - X[0]
tmp = []

if N==1:
    print(ans)
    sys.exit()


for i in range(1,M):
    tmp2 = X[i] - X[i-1]
    if len(tmp) < N-1:
        tmp.append(tmp2)
    else:
        tmp3 = min(tmp)
        if tmp3 < tmp2:
            tmp.remove(tmp3)
            tmp.append(tmp2)

print(ans - sum(tmp))
import itertools
n, m = map(int, input().split())
P = [input().split() for i in range(m)]
P = list(itertools.chain.from_iterable(P))
ac_list = []
wa_list = [0] * n

counta = 0
countb = 0
for i in range(1, m * 2, 2):
    if P[i] == "AC" and:
        if int(P[i - 1]) not in ac_list:
            counta += 1
            ac_list.append(int(P[i - 1]))
            countb += wa_list[int(P[i - 1]) - 1]
    else:
        wa_list[int(P[i - 1]) - 1] += 1
print(counta, countb)

### FIXED CODE ###

import itertools
n, m = map(int, input().split())
P = [input().split() for i in range(m)]
P = list(itertools.chain.from_iterable(P))
ac_list = [0] * n
wa_list = [0] * n
counta = 0
countb = 0
for i in range(1, m * 2, 2):
    if P[i] == "AC" and ac_list[int(P[i - 1])-1] == 0:
        counta += 1
        ac_list[int(P[i - 1])-1] = 1
        countb += wa_list[int(P[i - 1]) - 1]
    elif P[i] == "WA":
        wa_list[int(P[i - 1]) - 1] += 1
    else:
        continue

print(counta, countb)
s=input()
N=len(s)
a="Yes"

for i in range (0,N):
  if i%2=0:
    if (s[i]!="R") and (s[i]!="U") and (s[i]!="D"):
      a="No"
      break
  else:
    if (s[i]!="L") and (s[i]!="U") and (s[i]!="D"):
      a="No"
      break
print(a)
      
      
      

### FIXED CODE ###

s=input()
N=len(s)
a="Yes"

for i in range (0,N):
  if i%2==0:
    if (s[i]!="R") and (s[i]!="U") and (s[i]!="D"):
      a="No"
      break
  else:
    if (s[i]!="L") and (s[i]!="U") and (s[i]!="D"):
      a="No"
      break
print(a)
N = int(input())
A = list(input())
print(C[:C.count('R')].count("W"))


### FIXED CODE ###

n = int(input())
C = input()
print(C[:C.count('R')].count("W"))
n=int(input())
ans=0
ans=0
cnt=-(10**9)-1
cnt2=(10**9)*2
li=[]
li2=[]
for i in range(n):
    X,L=map(int,input().split())
    li.append([X-L,L])
    li2.append([X+L,L])
li=sorted(li,key=lambda x:x[0])
for i in range(n):
    if cnt>li[i][0]:
        ans+=1
    else:
        cnt=li[i][0]+li[i][1]*2
li2=sorted(li2,key=lambda x:x[0],reverse=True)
for i in range(1,n):
    if cnt2<li[i][0]:
        ans2+=1
    else:
        cnt2=li[i][0]-li[i][1]*2
print(n-min(ans,ans2))


### FIXED CODE ###

n=int(input())
ans=0
cnt=-(10**9)-1
li=[]
for i in range(n):
    X,L=map(int,input().split())
    li.append([X+L,L])
li=sorted(li,key=lambda x:x[0])
for i in range(n):
    if cnt>li[i][0]-li[i][1]*2:
        ans+=1
    else:
        cnt=li[i][0]
print(n-ans)
def e_virus_tree_2(N, K, Edges, MOD=10**9 + 7):
    graph = [[] for _ in range(N)]
    for a, b in Edges:
        graph[b - 1].append(a - 1)
        graph[a - 1].append(b - 1)

    def dfs(color, graph, current, parent):
        can_use_color_num = K - 1 if parent == -1 else K - 2

        if color < len(graph[current]):
            return 0  # 塗らねばならない子の数に対して色が足りない

        # コンビネーションの計算はここで行っている
        case_num = 1
        for child in graph[current]:
            if child == parent:
                continue
            case_num *= can_use_color_num
            case_num %= MOD
            can_use_color_num -= 1
        for child in graph[current]:
            if child == parent:
                continue
            case_num *= dfs(color, graph, child, current)
            case_num %= MOD
        return case_num

    ans = K * dfs(K, graph, 0, -1)
    return ans % MOD

N, K = [int(i) for i in input().split()]
Edges = [[int(i) for i in input().split()] for j in range(N - 1)]
print(e_virus_tree_2(N, K, Edges))

### FIXED CODE ###

def e_virus_tree_2(N, K, Edges, MOD=10**9 + 7):
    import sys
    sys.setrecursionlimit(10**6)
    
    graph = [[] for _ in range(N)]
    for a, b in Edges:
        graph[b - 1].append(a - 1)
        graph[a - 1].append(b - 1)

    def dfs(color, graph, current, parent):
        can_use_color_num = K - 1 if parent == -1 else K - 2

        if color < len(graph[current]):
            return 0  # 塗らねばならない子の数に対して色が足りない

        # コンビネーションの計算はここで行っている
        case_num = 1
        for child in graph[current]:
            if child == parent:
                continue
            case_num *= can_use_color_num
            case_num %= MOD
            can_use_color_num -= 1
        for child in graph[current]:
            if child == parent:
                continue
            case_num *= dfs(color, graph, child, current)
            case_num %= MOD
        return case_num

    ans = K * dfs(K, graph, 0, -1)
    return ans % MOD

N, K = [int(i) for i in input().split()]
Edges = [[int(i) for i in input().split()] for j in range(N - 1)]
print(e_virus_tree_2(N, K, Edges))
import math

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

a,b,c,d = map(int,input().split())
t = 0
l = b-a+1

c_count = (b // c) - ((a-1) // c)

d_count = (b // d) - ((a-1) // d)

cd = c * d
cd_count =  (b // cd) - ((a-1) // cd)

lc = lcm(c,d)
lc_count = (b // lc) - ((a-1) // lc)

print(l-c_count-d_count+cd_count+lc)

### FIXED CODE ###

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

a,b,c,d = map(int,input().split())
t = 0
l = b-a+1

c_count = (b // c) - ((a-1) // c)

d_count = (b // d) - ((a-1) // d)

lc = (c*d) // gcd(c,d)
lc_count = (b // lc) - ((a-1) // lc)

print(l-c_count-d_count+lc_count)
n = int(input())
s = input()
k = int(input())
for i in range(length(s))
	if s[i] != s[k-1]
  		s[i] = "*"
print(s)


### FIXED CODE ###

input()
S=input()
k=int(input())
for s in S:print(s if s==S[k-1] else "*",end="")
n=int(input().split())
a=n[0]
b=n[1]
S=a*b
L=(2*a)+(2*b)
print(S' 'L)


### FIXED CODE ###

#cording; UTF-8
a,b=[int(x) for x in input().split()]

S = a*b
L = 2*(a+b)
print(S,L)