Harryxun/GPT-100-sft-dataset huggingface dataset:
Problem p03049 (python)

Fixed submission:
n = int(input())
s_list = []
for _ in range(n):
    s_list.append(input())

ans = 0
head_b = 0
tail_a = 0
headAndTail = 0

for s in s_list:
    ans += s.count('AB')

    if s.startswith('B') and s.endswith('A'):
       headAndTail += 1
    elif s.startswith('B'):
        head_b += 1
    elif s.endswith('A'):
        tail_a += 1

ans += min([head_b, tail_a])

if head_b == 0 and tail_a == 0:
    ans += max([0,headAndTail-1])
else:
    ans += headAndTail

print(ans)

Buggy submission (verdict: Runtime Error):
n = int(input())
s_list = []
for _ in range(n):
    s_list.append(input())

ans = 0
head_b = 0
tail_a = 0
headAndTail = 0

for s in s_list:
    if 'AB' in s:
        ans += 1
    if s.startswith('B') and s.endswith('A')::
       headAndTail += 1
    elif s.startswith('B'):
        head_b += 1
    elif s.endswith('A'):
        tail_a += 1

ans += min([head_b, tail_a])

if head_b == 0 and tail_a == 0:
    ans += max([0,headAndTail-1])
else:
    ans += headAndTail

print(ans)
Problem p02995 (python)

Fixed submission:
from fractions import gcd

a,b,c,d=map(int, input().split())
tisai = int(c*d/gcd(c,d))
n=[c,d]
count=0
for k in range(2):
    count += ((b//n[k])-((a-1)//n[k]))
count -= ((b//tisai)-((a-1)//tisai))
print(int((b-a+1)-count))

Buggy submission (verdict: Runtime Error):
import math

a,b,c,d=map(int, input().split())
tisai = c*d/math.gcd(c,d)
n=[c,d]
count=0
for k in range(2):
    count+= ((b+1)//n[k])-(a//n[k])
    # print(count)
count-= ((b+1)//tisai)-(a//tisai)
# print(count)
print(int((b-a+1)-count))
Problem p03087 (python)

Fixed submission:
n,q = map(int, input().split())
s = input()
count = [0]*n
for i in range(1,n):
    count[i] += count[i-1]
    if s[i-1:i+1]=="AC": count[i]+=1
for i in range(q):
    l,r = map(int, input().split())
    print(count[r-1]-count[l-1])

Buggy submission (verdict: Runtime Error):
NQ = list(map(int, input().split()))
word = input()
word_list = [*word]
for i in range(0, NQ[1]):
    rl = list(map(int, input().split()))
    word = word_list[rl[0]-1:rl[1]]
    word = ''.join(word)
    print(word.count('AC'))
Problem p03129 (python)

Fixed submission:
N = list(map(int, input().split()))
if (2 * N[1] - 1 <= N[0]):
    print("YES")
else: 
    print("NO")

Buggy submission (verdict: Runtime Error):
N = int(input())
K = int(input())

if (2 * K - 1 <= N):
    print("YES")
else: 
    print("NO")
Problem p03293 (python)

Fixed submission:
S = tuple(input()) # これで文字列を一文字にできる
T = input()

for i in range(0, len(S)):
    word = ''
    for j in range(0, len(S)):
        index = (i + j) % len(S)
        word += S[index]
    if word == T:
        print('Yes')
        break
    elif i == j:
        print('No')
        break

Buggy submission (verdict: Runtime Error):
S = [*input()] # これで文字列を一文字にできる
T = input()

for i in range(0, len(S)):
    word = ''
    for j in range(0, len(S)):
        index = (i + j) % len(S)
        word += S[index]
    if word == T:
        print('Yes')
        break
    elif i == j:
        print('No')
        break

Buggy submission (verdict: Runtime Error):
S = [*input()] # これで文字列を一文字にできる
T = input()

for i in range(0, len(S)):
    word = ''
    for j in range(0, len(S)):
        index = (i + j) % len(S)
        word += S[index]
    if(word == T):
        print('Yes')
        break
    elif(i == j):
        print('No')
        break

Buggy submission (verdict: Runtime Error):
S = [*input()] # これで文字列を一文字にできる
T = input()
for i in range(0, len(S)):
    word = ''
    for j in range(0, len(S)):
        index = (i + j) % len(S)
        word += S[index]
    if(word == T):
        print('Yes')
        break
    elif(i == j):
        print('No')

Buggy submission (verdict: Runtime Error):
import sys

S = [*input()] # これで文字列を一文字にできる
T = input()
for i in range(0, len(S)):
    word = ''
    for j in range(0, len(S)):
        index = (i + j) % len(S)
        word += S[index]
    if(word == T):
        print('Yes')
        sys.exit()
print("No")
Problem p03352 (python)

Fixed submission:
n = int(input())
c = 1
for i in range(1, n):
    for j in range(2, n):
        if i**j<=n:
            c=max(c, i**j)
        else:break
print(c)

Buggy submission (verdict: Runtime Error):
n = int(input())
c = 1
for i in range(1, n):
    for j in range(2, n):
        if i**j<=x:
            c=max(c, i**j)
print(c)

Buggy submission (verdict: Runtime Error):
n = int(input())
c = 1
for i in range(1, n):
    for j in range(2, n):
        if i**j<=x:
            c=max(c, i**j)
print(c)
Problem p03361 (python)

Fixed submission:
h,w=map(int, input().split())
S=["."+input()+"." for _ in range(h)]
S = ["."*(w+2)]+S+["."*(w+2)]
# print(S)
flag=True
for i in range(h):
    for j in range(w):
        if S[i][j]=="#":
            if S[i-1][j]=="." and S[i+1][j]=="." and S[i][j-1]=="." and S[i][j+1]==".":
                flag=False
print("Yes" if flag else "No")

Buggy submission (verdict: Runtime Error):
h,w=map(int, input().split())
S=["."+input()+"." for _ in range(h)]
S = ["."*(w+2)]+S+["."*(w+2)]
# print(S)
flag=True
for i in range(h):
    for j in range(w):
        if S[i][j]=="#":
            if S[i-1][j]=="." and S[i+1][j]=="." and S[i][j-1]=="." and S[i][j+1]==".":
                flag=False
print("Yes" if flag else "No")a
Problem p03408 (python)

Fixed submission:
Ns = [input() for _ in range(int(input()))]
Ms = [input() for _ in range(int(input()))]
l = list(set(Ns))
print(max(0,max((Ns.count(l[i])-Ms.count(l[i]) for i in range(len(l))))))

Buggy submission (verdict: Runtime Error):
Ns = [input() for _ in range(int(input()))]
Ms = [input() for _ in range(int(input()))]
l = list(set(Ns))
print(max(0,max((Ns.count(l[i])-Ms.count(l[i]) for i in range(len(l))))))a
Problem p02995 (python)

Fixed submission:
import fractions
A, B ,C, D = list(map(int, input().split()))

lcm = C * D //fractions.gcd(C, D)
b =  B // C + B // D - B // lcm
b = B - b

A -= 1
a =  A // C + A // D - A // lcm
a = A - a

print(b - a)

Buggy submission (verdict: Runtime Error):
import math
A, B ,C, D = list(map(int, input().split()))

lcm = C * D //math.gcd(C, D)
b =  B // C + B // D - B // lcm
b = B - b

A -= 1
a =  A // C + A // D - A // lcm
a = A - a

print(b - a)
Problem p02995 (python)

Fixed submission:
from fractions import gcd
a, b, c, d = map(int, input().split())

a_c = (a-1)//c
a_d = (a-1)//d
gcd_dc = gcd(d,c)
lcm_dc = (c*d)//gcd_dc
a_cd = (a-1)//lcm_dc
b_c = b//c
b_d = b//d
b_cd = b//lcm_dc

print(b-a+1-(b_c+b_d-b_cd-a_c-a_d+a_cd))

Buggy submission (verdict: Runtime Error):
import math
a, b, c, d = map(int, input().split())

a_c = (a-1)//c
a_d = (a-1)//d
gcd_dc = math.gcd(d,c)
lcm_dc = (c*d)//gcd_dc
a_cd = (a-1)//lcm_dc
b_c = b//c
b_d = b//d
b_cd = b//lcm_dc

print(b-a+1-(b_c+b_d-b_cd-a_c-a_d+a_cd))
Problem p03061 (python)

Fixed submission:
N = int(input())
A = list(map(int, input().split()))

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

L = A.copy()
R = A.copy()
for i in range(1, N):
    L[i] = gcd(L[i-1], L[i])

for i in reversed(range(0, N-1)):
    R[i] = gcd(R[i+1], R[i])

result = max(R[1],L[-2])

for i in range(1, N-1):
    result = max(result, gcd(L[i-1],R[i+1]))
print(result)

Buggy submission (verdict: Runtime Error):
N = int(input())
A = list(map(int, input().split()))

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

r = 0
if N==1:
    print(A[0])
    exit()
else:
    r = gcd(A[0], A[1])
    if N==2:
        print(r)
        exit()
    else:
        for i in range(2, N):
            r = gcd(r,A[i])
B=[]
for i in A:
    B.append(i//r)
#print(B)
D={}
for i in range(N):
    p = B.pop(i)
    rr = gcd(B[0],B[1])
    if len(B)>2:
        for j in range(2,N):
            rr = gcd(rr,B[j])
    if rr not in D:
        D[rr]=1
    else:
        D[rr]+=1
    B.insert(i,p)
#print (D)
for i in D:
    if i ==N-1:
        print(r*i)
        exit()
print(r)
Problem p03105 (python)

Fixed submission:
a, b, c = map(int, input().split())
if(b/a>=c):
    print(c)
else:
    print(b//a)

Buggy submission (verdict: Runtime Error):
a, b, k = map(int, input().split())

div=[]
for i in range(1,min(a,b)+1):
    if(a%i==0 and b%i==0):
        div.append(i)
if(div):
    div.reverse()
    print(div[k-1])
else:
    print(1)
Problem p03106 (python)

Fixed submission:
a, b, k = map(int, input().split())

div=[]
for i in range(1,min(a,b)+1):
    if(a%i==0 and b%i==0):
        div.append(i)
if(div):
    div.reverse()
    print(div[k-1])
else:
    print(1)

Buggy submission (verdict: Runtime Error):
a, b, k = map(int, input().split())

div=[]
for i in range(1,max(a,b)):
    if(a%i==0 and b%i==0):
        div.append(i)
if(div):
    div.reverse()
    print(div[k-1])
else:
    print(1)
Problem p03264 (python)

Fixed submission:
K = int(input())
print((K//2)*(K//2 + K%2))

Buggy submission (verdict: Runtime Error):
a,b =map(int, input().split())
r = 0
for _ in range(2):
    if(a>b):
        r+=a
        a-=1
    else:
        r+=b
        b-=1
print(r)
Problem p03050 (python)

Fixed submission:
N = int(input())
ans = 0
l = list()
for i in range(1, int(N**0.5)+1):
  if N % i == 0:  # i is a divisor of N
    if i > 1:
      m = i-1
      if N//m == N % m:ans += m
    if i != N//i:
      m = N//i-1
      if N//m == N % m:ans += m
print(ans)

Buggy submission (verdict: Runtime Error):
N = int(input())
ans = 0
l = list()
for i in range(1, int(N**0.5)+1):
  if N % i == 0:  # i is a divisor of N
    if i > 1:
      m = i-1
      if N//m == N % m:ans += m
    m = N//i-1
    if N//m == N % m:ans += m
print(ans)
Problem p03069 (python)

Fixed submission:
n = int(input())
s = '.'+input()
lb, rw = 0, s.count('.')-1
ans = lb+rw
for i in range(1,n+1):
  if s[i] == '#':
    lb += 1
  elif s[i] == '.':
    rw -= 1
  if lb+rw < ans:
    ans = lb+rw
print(ans)

Buggy submission (verdict: Runtime Error):
n = int(input())
s = '.'+input()
ans = []

def div(i, s):
  l = s[:i.start()+1]
  r = s[i.end()-1:]
  lb = l.count('#')
  rw = r.count('.')
  return l, lb, r, rw
  
for i in re.finditer(r'#\.', s):
  l, lb, r, rw = div(i, s)
  ans.append(lb+rw)
for i in re.finditer(r'\.#', s):
  l, lb, r, rw = div(i, s)
  ans.append(lb+rw)
if len(ans) > 0:
  print(min(ans))
else:
  print(0)

Buggy submission (verdict: Runtime Error):
n = int(input())
s = '.'+input()
ans = []

def div(i, s):
  l = s[:i.start()+1]
  r = s[i.end()-1:]
  lb = l.count('#')
  rw = r.count('.')
  return l, lb, r, rw
  
for i in re.finditer(r'#\.', s):
  l, lb, r, rw = div(i, s)
  print(l, lb, r, rw)
  ans.append(lb+rw)
print()
for i in re.finditer(r'\.#', s):
  l, lb, r, rw = div(i, s)
  print(l, lb, r, rw)
  ans.append(lb+rw)
print('\n',ans)
if len(ans) > 0:
  print(min(ans))
else:
  print(0)

Buggy submission (verdict: Runtime Error):
import re
n = int(input())
s = input()
anss = []
for i in re.finditer(r'#\.|\.#', s):
  l = s[:i.start()+1]
  r = s[i.end()-1:]
  anss.append(l.count('#')+r.count('.'))
print(min(anss))

Buggy submission (verdict: Runtime Error):
n = int(input())
s = input()
anss = []
for i in re.finditer(r'#\.|\.#', s):
  l = s[:i.start()+1]
  r = s[i.end()-1:]
  anss.append(l.count('#')+r.count('.'))
print(min(anss))

Buggy submission (verdict: Runtime Error):
n = int(input())
s = input()

def next(s):
  if s == '':  # empty
    return 0, 0, None
  if len(s) == s.count('.') or len(s) == s.count('#'):  # . or # only
    return s.count('#'), s.count('.'), ''

  l = s.index('#')
  if s.count('#.') > 0:
    c = s.index('#.')+1
    if s.count('.#') > 0:
      r = s.index('.#')+1
    else:
      r = len(s)-1
  else:
    c,r = len(s)-1
  b = c - l
  w = r - c
  return b, w, s[r:]

black, white = 0, 0
if s[0] != '#':
  s = s[s.index('.#')+1:]
while(s != None):
  b, w, s = next(s)
  black += b
  white += w
print(min(black, white))
Problem p03076 (python)

Fixed submission:
a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())

l = []
ans = 0
for t in [a,b,c,d,e]:
  if t%10 == 0:
    ans += t
  else:
    l.append(t)

if len(l) < 1:
  print(ans)
elif len(l) == 1:
  print(ans + l[0])
else:
  l = sorted(l, key=lambda x: x%10, reverse=True)

  def tyumon(t, ans):
    ans += t
    if ans % 10 == 0:
      return ans
    else:
      return (ans//10 + 1)*10

  for i in range(len(l)-1):
    ans = tyumon(l[i], ans)
  print(ans + l[-1])

Buggy submission (verdict: Runtime Error):
a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())

l = []
ans = 0
for t in [a,b,c,d,e]:
  if t%10 == 0:
    ans += t
  else:
    l.append(t)

if len(l) < 1:
  print(ans)10
elif len(l) == 1:
  print(ans + l[0])
else:
  l = sorted(l, key=lambda x: x%10, reverse=True)

  def tyumon(t, ans):
    ans += t
    if ans % 10 == 0:
      return ans
    else:
      return (ans//10 + 1)*10

  for i in range(len(l)-1):
    ans = tyumon(l[i], ans)
  print(ans + l[-1])

Buggy submission (verdict: Runtime Error):
a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())

l = []
ans = 0
for t in [a,b,c,d,e]:
  if t%10 == 0:
    ans += t
  else:
    l.append(t)
    
l = sorted(l, key=lambda x: x%10, reverse=True)

def tyumon(t, ans):
  ans += t
  if ans % 10 == 0:
    return ans
  else:
    return (ans//10 + 1)*10

for i in range(len(l)-1):
  ans = tyumon(l[i], ans)
print(ans + l[-1])

Buggy submission (verdict: Runtime Error):
a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())

l = [a,b,c,d,e]
nl = []
ans = 0
for t in l:
  if t%10 == 0:
    ans += t
  else:
    nl.append(t)
    
nl = sorted(nl, key=lambda x: x%10, reverse=True)

def tyumon(t, ans):
  ans += t
  if ans % 10 == 0:
    return ans
  else:
    return (ans//10 + 1)*10

for i in range(len(nl)-1):
  ans = tyumon(nl[i], ans)
print(ans + nl[-1])
Problem p03095 (python)

Fixed submission:
N=int(input())
S=input()
ans=1
for c in set(S):
  ans *= (S.count(c)+1)
print((ans-1) % (10**9+7))

Buggy submission (verdict: Runtime Error):
nCr={}
def cmb(n, r):
  if r==0 or r==n:
    return 1
  if r==1 or n-r==1:
    return n
  if (n,r) in nCr:
    return nCr[(n,r)]
  nCr[(n,r)] = cmb(n-1,r)+cmb(n-1,r-1)
  return nCr[(n,r)]

N=int(input())
S=input()
ans=N
for r in range(2, N+1):
  ans+=cmb(N, r)

str_num = {i: S.count(i) for i in set(S) if S.count(i) > 1}
for s, n in str_num.items():
  ans -= 2**(N-n)
if len(str_num) > 1:
  ans += 2**(N-sum(str_num.values()))

print(ans)

Buggy submission (verdict: Runtime Error):
N=int(input())
S=input()
ans=N
for i in range(2, N+1):
  sub=[x for x in list(itertools.combinations(S, i)) if len(x) == len(set(x))]
  ans+=len(sub)
print(ans)

Buggy submission (verdict: Runtime Error):
N=int(input())
S=input()
ans=N
for i in range(2, N+1):
  sub=[x for x in list(itertools.combinations(S, i)) if len(x) == len(set(x))]
  ans+=len(sub)
  print(sub, ans)
Problem p03032 (python)

Fixed submission:
def main():
    N, K = map(int, input().split())
    V = [int(v) for v in input().split()]

    m = 0 
    r = min(N, K)
    for a in range(r+1):
        for b in range(r+1-a):
            if b == 0:
                v = V[:a]
            else:
                v = V[:a] + V[-b:]
            v.sort()    
            for i in range(K+1-a-b):
                if i >= len(v):
                    break
                if  v[i] >= 0:
                    break
            s = sum(v[i:])
            if s > m:
                m = s

    print(m)


main()

Buggy submission (verdict: Runtime Error):
def main():
    N, K = map(int, input().split())
    V = [int(v) for v in input().split()]

    m = 0

    r = min(N, K)
    for a in range(r+1):
        for b in range(r+1-a):
            if b == 0:
                v = V[:a]
            else:
                v = V[:a] + V[-b:]
            v.sort()    
            for i in range(K-a-b):
                if v[i] >= 0:
                    break
            s = sum(v[i:])
            if s > m:
                m = s

    print(m)


main()
Problem p03061 (python)

Fixed submission:
import fractions
from functools import reduce


def main():

    N = int(input())
    A = [int(a) for a in input().split()]

    gcds_r = [1] * N
    gcds_r[0] = A[0]
    for n in range(1, N):
        gcds_r[n] = fractions.gcd(gcds_r[n-1], A[n])

    gcds_l = [1] * N
    gcds_l[-1] = A[-1]
    for n in range(N-1)[::-1]:
        gcds_l[n] = fractions.gcd(gcds_l[n+1], A[n])

    max_gcd = 1
    for n in range(1, N-1):
        max_gcd = max(max_gcd, fractions.gcd(gcds_r[n-1], gcds_l[n+1]))

    max_gcd = max(max_gcd, gcds_l[1], gcds_r[N-2])

    print(max_gcd)  


main()

Buggy submission (verdict: Runtime Error):
import math
from functools import reduce


def main():

    N = int(input())
    A = [int(a) for a in input().split()]

    maxd = 1
    for n in range(N):
        l = A[:n] + A[n+1:]
        maxd = max(maxd, gcd(*l))

    print(maxd)    


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


main()
Problem p03043 (python)

Fixed submission:
import math

N, K = map(int, input().split())
p = 0

count = 1
while True:
    p += max(0, min(N + 1, math.ceil(K / 2 ** (count - 1))) - math.ceil(K / 2 ** count)) * 0.5 ** count
    count += 1
    if K / 2 ** count < 0.5:
        break

p += max(0, N - K + 1)
print(p / N)

Buggy submission (verdict: Runtime Error):
import math

N, K = map(int, input().split())
p = 0

for i in range(1, min(K, N + 1)):
    print(math.ceil(math.log2(K / i)))
    p += 2 ** (-math.ceil(math.log2(K / i)))

p += max(0, N - K + 1)
print(p / N)
Problem p02999 (python)

Fixed submission:
[x,a]=[int(i) for i in input().split()]

if a>x:
    print(0)
else:
    print(10)

Buggy submission (verdict: Runtime Error):
x=input()
a=input()

if a>x:
    print(0)
else:
    print(10)
Problem p03000 (python)

Fixed submission:
[n,x]=[int(i) for i in input().split()]
l=[int(i) for i in input().split()]
sum=int(0)
count = int(0)

while count<n and sum+l[count]<=x:
    sum=sum+l[count]
    count=count+1

print(count+1)

Buggy submission (verdict: Runtime Error):
[n,x]=[int(i) for i in input().split()]
l=[int(i) for i in input().split()]
sum=int(0)
count = int(0)

while count<n && sum+l[count]<=x:
    sum=sum+l[count]
    count=count+1

print(count+1)

Buggy submission (verdict: Runtime Error):
[n,x]=[int(i) for i in input().split()]
l=[int(i) for i in input().split()]
sum=int(0)
count = int(0)

while sum+l[count]<=x:
    sum=sum+l[count]
    count=count+1

print(count+1)

Buggy submission (verdict: Runtime Error):
[n,x]=[int(i) for i in input().split()]
l=[int(i) for i in input().split()]
sum=int(0)
count = int(1)

while sum+l[count-1]<=x:
    sum=sum+l[count-1]
    count=count+1
    
print(count)

Buggy submission (verdict: Runtime Error):
[n,x]=[int(i) for i in input().split()]
l=[int(i) for i in input().split()]
sum=int(0)
count = int(1)

while sum+l[count-1]<=x:
    sum=sum+l[count-1]
    count=count+1
    print(sum)
    print(count)


print(count)
Problem p03001 (python)

Fixed submission:
[w,h,x,y]=[int(i) for i in input().split()]

a=int(0)

if x*2==w and y*2==h:
    a=int(1)
else:
    a=int(0)

print(str(w*h/2)+" "+str(a))

Buggy submission (verdict: Runtime Error):
[w,h,x,y]=[int(i) for i in input().split()]

a=int(0)

if x*2==w and y*2==h:
    a=int(1)
else:
    a=int(0)

print(double(w*h/2)+" "+a)

Buggy submission (verdict: Runtime Error):
[w,h,x,y]=[int(i) for i in input().split()]


if x*2==w and y*2==h:
    ans=int(1)
else ans=int(0)

print(double(w*h/2)+" "+ans)

Buggy submission (verdict: Runtime Error):
[w,h,x,y]=[int(i) for i in input().split()]


if x*2=w and y*2=h:
    ans=int(1)
else ans=int(0)

print(double(w*h/2)+" "+ans)

Buggy submission (verdict: Runtime Error):
[w,h,x,y]=[int(i) for i in input().split()]

print(double(w*h/2))
if x*2=w and y*2=h:
    print(1)
else print(0)
Problem p02985 (python)

Fixed submission:
import sys
sys.setrecursionlimit(200000)

nl = lambda: list(map(int, input().split()))
sl = lambda: input().split()
n = lambda: int(input())
s = lambda: input()

N, K = nl()

from collections import defaultdict
edges = defaultdict(set)
for i in range(N-1):
    a, b = nl()
    edges[a].add(b)
    edges[b].add(a)


done = [False] * (N+1)
done[1] = True

def find(i, cands, prev):
    res = cands

    count = 0
    if prev:
        count += 1
    for edge in edges[i]:
        if done[edge]:
            continue
        count += 1
        done[edge] = True
        res *= find(edge, K - count, True)
        res %= 1000000007
    return res


print(find(1, K, False))

Buggy submission (verdict: Runtime Error):

nl = lambda: list(map(int, input().split()))
sl = lambda: input().split()
n = lambda: int(input())
s = lambda: input()

N, K = nl()

from collections import defaultdict
edges = defaultdict(set)
for i in range(N-1):
    a, b = nl()
    edges[a].add(b)
    edges[b].add(a)


done = [False] * (N+1)
done[1] = True

def find(i, cands, prev):
    res = cands

    count = 0
    if prev:
        count += 1
    for edge in edges[i]:
        if done[edge]:
            continue
        count += 1
        done[edge] = True
        res *= find(edge, K - count, True)
        res %= 1000000007
    return res


print(find(1, K, False))

Buggy submission (verdict: Runtime Error):

nl = lambda: list(map(int, input().split()))
sl = lambda: input().split()
n = lambda: int(input())
s = lambda: input()

N, K = nl()

from collections import defaultdict
edges = defaultdict(set)
for i in range(N-1):
    a, b = nl()
    edges[a].add(b)
    edges[b].add(a)


done = [False] * (N+1)
done[1] = True

def find(i, cands, prev):
    res = cands

    count = 0
    if prev:
        count += 1
    for edge in edges[i]:
        if done[edge]:
            continue
        count += 1
        done[edge] = True
        res *= find(edge, K - count, True)
    return res % 1000000007


print(find(1, K, False))

Buggy submission (verdict: Runtime Error):

nl = lambda: list(map(int, input().split()))
sl = lambda: input().split()
n = lambda: int(input())
s = lambda: input()

N, K = nl()

from collections import defaultdict
edges = defaultdict(set)
for i in range(N-1):
    a, b = nl()
    edges[a].add(b)
    edges[b].add(a)


done = [False] * (N+1)
done[1] = True

def find(i, cands, prev):
    res = cands

    count = 0
    if prev:
        count += 1
    for edge in edges[i]:
        if done[edge]:
            continue
        count += 1
        done[edge] = True
        res *= find(edge, K - count, True)
    return res % 1000000007


print(find(1, K, False))