Harryxun/stf_run huggingface dataset:
def main120():
    import sys
    S_org = input()
    S = []

    for s in range(len(S_org)):
        S.append(S_org[s])
    S = list(map(int, S))

    cont = True
    index = 0
    count = 0

    if len(S) == 1:
        print(0)
        sys.exit()

    else:
        while(cont):
            print(index)
            if S[index] == S[index+1]:
                index += 1
            else:
                count += 2
                S.pop(index)
                S.pop(index)
                if index > 0:
                    index -= 1

            if index == len(S) - 2:
                if S[index] != S[index+1]:
                    count += 2
                print(count)
                sys.exit()


main120(

### FIXED CODE ###

def main120():
    import sys
    S_org = input()
    S = []

    for s in range(len(S_org)):
        S.append(S_org[s])
    S = list(map(int, S))

    cont = True
    index = 0
    count = 0

    if len(S) == 1:
        print(0)
        sys.exit()

    else:
        while(cont):
            if S[index] == S[index+1]:
                index += 1
            else:
                count += 2
                S.pop(index)
                S.pop(index)
                if index > 0:
                    index -= 1

            if index == len(S) - 2:
                if S[index] != S[index+1]:
                    count += 2
                print(count)
                sys.exit()


main120()
N = int(input())
A = list(map(int, input().split()))
bottom = sum(A)

if N == 0:
  if A[0] != 1:
    print(-1)
  else:
    print(1)
  exit()
 
ret = 1
children = 1 - A[0]
bottom -= A[0]
 
for i in range(N):
    children = children * 2 - A[i+1]
    if children <= -1:
      ret = -1
      break
    
    bottom -= A[i+1]
    if children >= bottom:
      children = bottom
    ret += children + A[i+1]
print(ret)


### FIXED CODE ###

h1, m1, h2, m2, k=map(int, input().split())

print((h2-h1)*60+(m2-m1)-k)
N,M,X = map(int,input().split())
C = []
A = []
success = []

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

C.sort()
n = len(C)
items = []
for i in range(2 ** n):
    item = []
    for j in range(n):  # このループが一番のポイント
        if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
            item.append(C[j])  # フラグが立っていたら bag に果物を詰める
    items.append(item)

for i in range(1,len(items)):
    sum = 0
    a1 = 0
    a2 = 0
    a3 = 0
    for j in range(len(items[i])):
        index = items[i][j][1]
        a1 += A[index][0]
        a2 += A[index][1]
        a3 += A[index][2]
        sum += items[i][j][0]
    if a1 >= X and a2 >= X and a3 >= X:
        success.append(sum)
if len(success) == 0:
    print(-1)
else:
    print(min(success))

### FIXED CODE ###

from itertools import  product
N,M,X = map(int,input().split())
ca = [list(map(int,input().split())) for _ in range(N)]
for i in range(1,M+1):
    count=0
    for j in range(N):
        count+=ca[j][i]
    if count<X:
        print(-1)
        exit()

ans = 10**9
for z in product((0, 1), repeat=N):#bit全探索のくみあわせを勝手に作ってくれるので使うとよい
    count=0
    count2=[0]*M
    for i in range(N):
        if z[i]==1:
            count+=ca[i][0]
            for j in range(1,M+1):
                count2[j-1]+=ca[i][j]
    
    for i in range(M):
        if count2[i]<X:
            break
    else:
        ans=min(count,ans)
print(ans)
N, M = map(int, input().split())
As = list(map(int, input().split()))

mvals = list(np.array(As) * (-1))
import heapq
heapq.heapify(mvals)

for _ in range(M):
    price = heapq.heappop(mvals)
    heapq.heappush(mvals, price / 2)

res = (np.array(mvals) * (-1)).astype(int).sum()
print(res)

### FIXED CODE ###

N, M = map(int, input().split())
mvals = list(map(lambda x: -int(x), input().split()))

import heapq
heapq.heapify(mvals)

for _ in range(M):
    price = heapq.heappop(mvals)
    heapq.heappush(mvals, price / 2)

res = sum(map(lambda x:int(-x), mvals))
print(res)
import sys
s = sys.stdin.readlines()
A1_1,A1_2,A1_3= map(int, s[0].split())
A2_1,A2_2,A2_3= map(int, s[1].split())
A3_1,A3_2,A3_3= map(int, s[2].split())
N=int(s[3].split())
B=[]
for e in s[4:N + 4]:
    B.append(e)
a=str('yes')
b=str('no')
if A1_1 in B and A1_2 in B and A1_3 in B:
     print(a)
elif A2_1 in B and A2_2 in B and A2_3 in B:
    print(a)
elif A3_1 in B and A3_2 in B and A3_3 in B:
     print(a)
elif A1_1 in B and A2_1 in B and A3_1 in B:
    print(a)
elif A1_2 in B and A2_2 in B and A3_2 in B:
    print(a)
elif A1_3 in B and A2_3 in B and A3_3 in B:
    print(a)
elif A1_1 in B and A2_2 in B and A3_3 in B:
     print(a)
elif A1_3 in B and A2_2 in B and A3_1 in B:
    print(a)
else:
    print(b)

### FIXED CODE ###

A1_1,A1_2,A1_3 = map(int, input().split())
A2_1,A2_2,A2_3 = map(int, input().split())
A3_1,A3_2,A3_3 = map(int, input().split())
N =int(input())
B = []
for _ in range(N):
    B.append(int(input()))

a=str('Yes')
b=str('No')
if A1_1 in B and A1_2 in B and A1_3 in B:
     print(a)
elif A2_1 in B and A2_2 in B and A2_3 in B:
    print(a)
elif A3_1 in B and A3_2 in B and A3_3 in B:
     print(a)
elif A1_1 in B and A2_1 in B and A3_1 in B:
    print(a)
elif A1_2 in B and A2_2 in B and A3_2 in B:
    print(a)
elif A1_3 in B and A2_3 in B and A3_3 in B:
    print(a)
elif A1_1 in B and A2_2 in B and A3_3 in B:
     print(a)
elif A1_3 in B and A2_2 in B and A3_1 in B:
    print(a)
else:
    print(b)
a=raw_input() 
if a[-1] =="s": 
  print a+"es"
elss:
  print a+"s"
  

### FIXED CODE ###

a=raw_input()
if a[-1]=='s':
    print (a+"es")
else: 
    print (a+"s")
N, K = map(int, input().split())
dices = list(map(int, input().split()))

exv = [(e+1)/2 for e in dices]
temp = sum(m[0:K])
result = temp
for i in range(N-K):
    temp -= dices[i]
    temp += dices[i+K]
    if temp > result:
        result = temp
print(result)

### FIXED CODE ###

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

exv = [(e+1)/2 for e in dices]
temp = sum(exv[0:K])
result = temp
for i in range(N-K):
    temp -= exv[i]
    temp += exv[i+K]
    if temp > result:
        result = temp
print(result)
N,Q=map(int,input().split())
s=input()
for i in range(Q):
  l,r=map(int,input().split())
  print(s[l-1:r].count("AC")

### FIXED CODE ###

N,Q=map(int,input().split())
s=input()
A=[0]
for i in range(N-1):
  if s[i]+s[i+1]=="AC":
    A.append(A[i]+1)
  else:
    A.append(A[i])
for i in range(Q):
  l,r=map(int,input().split())
  print(A[r-1]-A[l-1])
N,X = map(int, input().split())
List = [int(x) for x in input().split()]
 
import math
List.append(X)
List.sort()
 
distance = []
for i in range(N):
    distance.append(List[i+1]-List[i])
 
d_min = min(distance)
 
num_list = []
 
c = 1
while c <= math.sqrt(d_min):
    if d_min%c == 0:
        num_list.append(c)
    c += 1
 
num_list2 = [1]*len(num_list)
for i in range(len(num_list)):
    num_list2[len(num_list)-i-1] = int(d_min/num_list[i])
 
num_list = num_list + num_list2
 
 
j = len(num_list)-1
c2 = 0
while j >= 0:
    for k in range(len(distance)):
        if distance[k]%num_list[j] == 0:
            c2 += 1
    if c2 == len(distance):
        ans = num_list[j]
        j = 0
    j -= 1
 
print(int(ans))

### FIXED CODE ###

N,X = map(int, input().split())
List = [int(x) for x in input().split()]
 
import math
List.append(X)
List.sort()
 
distance = []
for i in range(N):
    distance.append(List[i+1]-List[i])
 
d_min = min(distance)
 
num_list = []
 
c = 1
while c <= math.sqrt(d_min):
    if d_min%c == 0:
        num_list.append(c)
    c += 1
 
num_list2 = [0]*len(num_list)
for i in range(len(num_list)):
    num_list2[len(num_list)-i-1] = int(d_min/num_list[i])
 
num_list = num_list + num_list2

num_list.append(d_min)

j = len(num_list)-1

while j >= 0:
    c2 = 0
    for k in range(len(distance)):
        if distance[k]%num_list[j] == 0:
            c2 += 1
    if c2 == len(distance):
        ans = num_list[j]
        j = 0
    j -= 1
 
print(ans)
A = input()

if A == "Sunny":
    print("Cloudy")
else A == "Cloudy":
    print("Rainy")
else:
    print("Sunny")


### FIXED CODE ###

A = input()

if A == "Sunny":
    print("Cloudy")
elif A == "Cloudy":
    print("Rainy")
else:
    print("Sunny")
a=input()
b=input()
print a*b
print 2*a+2*b

### FIXED CODE ###

a = map(int, raw_input().split())
print a[0]*a[1],2*a[0]+2*a[1]
n,m = map(int, input().split())
sc = [ list(map(int,input().split())) for _ in range(m)]

ans = [0] * n
change_cnt = [0] * n
if n >= 2:
    ans[0]=1
for i in range(n):
    for j in range(m):
        if i+1 == sc[j][0]:
            if ans[i] != sc[j][1]:
                ans[i] = sc[j][1]
                change_cnt[i] += 1
                if change_cnt[i] > 1:
                    print(-1)
                    exit()

if n>=2:
    if ans[0]==0:
        print(-1)
        exti()

answer = ''
for i in range(len(ans)):
    answer += str(ans[i])

print(int(answer))


### FIXED CODE ###

n,m = map(int, input().split())
sc = [ list(map(int,input().split())) for _ in range(m)]

ans = [0] * n
change_cnt = [0] * n
if n >= 2:
    ans[0]=1
for i in range(n):
    for j in range(m):
        if i+1 == sc[j][0]:
            if ans[i] != sc[j][1]:
                ans[i] = sc[j][1]
                change_cnt[i] += 1
                if change_cnt[i] > 1:
                    print(-1)
                    exit()

if n>=2:
    if ans[0]==0:
        print(-1)
        exit()

answer = ''
for i in range(len(ans)):
    answer += str(ans[i])

print(int(answer))
x = input()

ans = x * x * x

print(ans)


### FIXED CODE ###

x = int(input())

ans = x * x * x

print(ans)
s,t=map(int,input().split())
ans=0
for i in range(3):
	if s[i]==t[i]:
		ans+=1
print(nas)

### FIXED CODE ###

s=input()
t=input()
ans=0
for i in range(3):
	if s[i]==t[i]:
		ans+=1
print(ans)
s=input()
if s ==　Sunny:
    print("Cloudy")
if s ==　Cloudy:
    print("Rainy")
else:
    print("Sunny")


### FIXED CODE ###

s=input()
if s=="Sunny":
  print("Cloudy")
if s=="Cloudy":
  print("Rainy")
if s=="Rainy":
  print("Sunny")
N = int(input())
A = sorted[input() for _ in range(N)]
print(len(set(A)))


### FIXED CODE ###

N = int(input())
A = sorted([input() for _ in range(N)])
print(len(set(A)))
N, M = map(int, input().split())
PY = [None for _ range(M)]
ken_d = {k:[]  for k in range(1, N+1)}

for i in range(M):
    p = list(map(int,input().split()))
    PY[i] = p
    ken_d[p[0]].append(p[1])

for k in ken_d.keys():
    ken_d[k].sort()

for p in PY:
    x = ken_d[p[0]].index(p[1]) + 1
    print(str(p[0]).zfill(6) + str(x).zfill(6))

### FIXED CODE ###

N, M = map(int, input().split())
import sys
PY = [list(map(int,sys.stdin.readline().rstrip().split())) for _ in range(M)]

# ken = {p[0] for p in PY}
# ken_d = {k:[] for k in ken}
ken_d = [[] for _ in range(N+1)]

rankdic = {} # 通し番号：県における順位

for i, p in enumerate(PY):
    # print(p)
    ken_d[p[0]].append([i, p[1]])

for k in range(N+1):
    ken_d[k].sort(key=lambda x:x[1])
    for i, v in enumerate(ken_d[k]):
        rankdic[v[0]] = i # 通し番号辞書に入れる

for i, p in enumerate(PY):
    x = rankdic[i] + 1
    print(str(p[0]).zfill(6) + str(x).zfill(6))
N,A,B = map(int, input().split())

NxA = (N*A)

if NxA =< B:
    print(NxA)
else:
    print(B)


### FIXED CODE ###

N,A,B = map(int, input().split())

N_A = (N*A)

if N_A <= B:
    print(N_A)
else:      
    print(B)
n = int(input())
list_d = list(map(int, input().split()))
new_list_d = set(list_d)
sum1 = len(list(new_list_d))
print(sum1)

### FIXED CODE ###

s = input()
print(s.replace('2017', '2018'))
K = int(input())
S = input()
if int(len(S)) <= K:
  print(S)
else:
  for i in range(len(S))
  	if i <= K:
      print(S[i],end="")
    else:
      print("...")
      break

### FIXED CODE ###

K = int(input())
S = input()
if int(len(S)) <= K:
  print(S)
else:
  for i in range(len(S)):
    if i < K:
      print(S[i],end="")
    else:
      print("...")
      break
#B
n, x = map(int, input().split())
l = list(map(int, input().split()))
d = 0
count=1
for i in range(n+1):
    d = d + l[i]
    if d > x:
        break
    count+=1
print(count)

### FIXED CODE ###

#B
n, x = map(int, input().split())
l = list(map(int, input().split()))
d = [0] * (n + 1)
d[0]=0
count = 0
for i in range(n):
    d[i + 1] = d[i] + l[i]
for i in d:
    if i <= x:
        count+=1
print(count)
x1,y1,x2,y2 = map(int,input().split())
distance = ( (x1 - x2)**2 + (y1 - y2)**2 )**(1/2)
print('{}'.format(distance))


### FIXED CODE ###

x1,y1,x2,y2 = map(float,input().split())
distance = ( (x1 - x2)**2 + (y1 - y2)**2 )**(1/2) 
print('{}'.format(distance))
a,b=map(int,raw_input().split());print(abs(a-b)<2and'Brown'or'Alice')

### FIXED CODE ###

a,b=map(int,raw_input().split());print abs(a-b)<2and'Brown'or'Alice'
a = random(1,10000)
b = random(1,10000)
if a * b %= 0:
  print('Even')
else:
  print('Odd')

### FIXED CODE ###

a, b = map(int, input().split())
if a * b % 2 == 0:
  print('Even')
else:
  print('Odd')
N,K=map(int,input().split())
A=list(map(int,input().split()))
A+=[0]*N
dp=[float("INF")]*(2N)
dp[0]=0
for i in range(N):
  for j in range(K):
    dp[i+j]=min(abs(A[i+j]-A[i])+dp[i],dp[i+j])
print(dp[N-1])

### FIXED CODE ###

N,K=map(int,input().split())
A=list(map(int,input().split()))
dp=[float("INF")]*(N+1)
dp[0]=0
for i in range(N):
  for j in range(1,K+1):
    if j+i>=N:
      break
    dp[i+j]=min(abs(A[i+j]-A[i])+dp[i],dp[i+j])
print(dp[N-1])
n, k = map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))

maxcost = -float('inf')
for pi in p:    # O(n^2)
    curr, costs = pi, [0]
    while pi != p[curr-1]:
        curr = p[curr-1]
        costs.append(costs[-1]+c[curr-1])
    loopsum = costs[-1]+c[pi-1]
    if loopsum > 0:
        maxcost = max(maxcost, loopsum*(k//len(costs))+max(costs[1:k % len(costs)+1]))
    else:
        maxcost = max(maxcost, max(costs[1:min(k, n)+1]))

print(maxcost)


### FIXED CODE ###

import numpy as np
 
n, k = map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))
 
cycles, check = [], [False]*n
for pi in p:
    if not check[pi-1]:
        curr, cycle = pi, []
        check[pi-1] = True
        while pi != p[curr-1]:
            check[curr-1] = True
            cycle.append(c[curr-1])
            curr = p[curr-1]
        check[curr-1] = True
        cycles.append(cycle + [c[curr-1]])
 
scores = []
for cycle in (np.array(cycle) for cycle in cycles):
    for i in range(cycle.size):
        cum = np.roll(cycle, i).cumsum()
        if cum[-1] > 0 and k > cycle.size:
            scores.append(cum[-1]*(k//cycle.size-1) + np.concatenate([cum, cum[:k % cycle.size]+cum[-1]]).max())
        else:
            scores.append(cum[:min(k, cum.size)].max())
print(max(scores))
import sympy
sympy.divisors(10**9)


def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

n =int(input())
ans = 0
for i in range(1,n,1):
    ans += i*len(make_divisors(i))

print(ans)

### FIXED CODE ###


n =int(input())

sum = 0
for i in range (1,n+1,1):
    k= n//i
    sum += int(i*k*(k+1)/2)

print(sum)
import sys
import math
k = int（sys.stdin.readline())
a = 1
t = 0
while a <= k:
  b = 1
  while b <= k:
    c = 1
    while c <= k:
      t += math.gcd(a,b,c)
      c += 1
    b += 1
  a += 1
print(t)

### FIXED CODE ###

import sys
import math
k = int(sys.stdin.readline())
a = 1
t = 0
while a <= k:
  b = 1
  while b <= k:
    c = 1
    while c <= k:
      t += math.gcd(math.gcd(a,b), c)
      c += 1
    b += 1
  a += 1
print(t)
h, w = map(int, input().split())
masu = [[0 for y in range(h)] for x in range(w)]
for y in range(0, h):
    z = list(input())
    for x in range(0, w):
        masu[y][x] = z[x]
hantei = "Yes"
for y in range(0, h):
    for x in range(0, w):
        if (masu[y][x] == "#"):
            if (not((y > 0 and masu[y - 1][x] == "#") or (y < h - 1 and masu[y + 1][x] == "#") or (x > 0 and masu[y][x - 1] == "#") or (x < w - 1 and masu[y][x + 1] == "#"))):
                hantei = "No"
print (hantei)

### FIXED CODE ###

h, w = map(int, input().split())
masu = [[0 for x in range(w)] for y in range(h)]
for y in range(0, h):
    z = list(input())
    for x in range(0, w):
        masu[y][x] = z[x]
hantei = "Yes"
for y in range(0, h):
    for x in range(0, w):
        if (masu[y][x] == "#"):
            if (not((y > 0 and masu[y - 1][x] == "#") or (y < h - 1 and masu[y + 1][x] == "#") or (x > 0 and masu[y][x - 1] == "#") or (x < w - 1 and masu[y][x + 1] == "#"))):
                hantei = "No"
print (hantei)
N,M = map(int, input().split())
p = [0]*M
S = [0]*M
for i in range(M):
    p[i],S[i] = input().split()
q = [int(s) for s in p]
X = [0]*N
Y = [0]*N
A = 0
B = 0
for i in range(M):
    if S[i] == "AC":
        if Y[q[i]]==0:
            Y[q[i]]+=1
            A += 1
            B += X[q[i]]
    else:
        if Y[q[i]]==0:
            X[q[i]] += 1
print(str(A)+" "+str(B))      

### FIXED CODE ###

N,M = map(int, input().split())
p = [0]*M
S = [0]*M
for i in range(M):
    p[i],S[i] = input().split()
q = [int(s)-1 for s in p]
X = [0]*N
Y = [0]*N
A = 0
B = 0
for i in range(M):
    if S[i] == "AC":
        if Y[q[i]]==0:
            Y[q[i]]+=1
            A += 1
            B += X[q[i]]
    else:
        if Y[q[i]]==0:
            X[q[i]] += 1
print(str(A)+" "+str(B))
K = int(input())
firsta = 7 % K
if firsta == 0:
    print(1)
elif firsta == 77 % K:
    print(-1)
else:
    ans = 2
    preva = 77 % K
    while preva != firsta and preva != 0:
        preva = ((preva*10)+7) % K
        ans += 1
        if preva = firsta:
            ans = -1
    print(ans)

### FIXED CODE ###

K = int(input())
def check(k):
    aaa = 0
    prev = 7%k
    for i in range(0,k):
        aaa+=1
        if prev == 0:
            return(aaa)
        prev = (prev*10+7)%k
    return(-1)
print(check(K))
n,k=map(int,input().split())
a=[0]*n
for i in range(k,n+2):
  a[i-k]=n*i-i**2+i+1

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




### FIXED CODE ###

n,k=map(int,input().split())
a=[0]*(n+1)
for i in range(k,n+2):
  a[i-k]=(n*i-i**2+i+1)%(10**9+7)

print(sum(a)%(10**9+7))
N, M = list(map(int, input().split(" ")))
list_a = list(map(int, input().split(" ")))

##最大公約数を求める

def gcd(a, b) :
  if(b==0) :
    return a
  else :
    t = a - b
    if(m > t) :
      return gcd(m, t)
    else :
      return(b, a%b)
   
##最小公倍数を求める
def lcm(a, b) :
  return a * b / gcd(a, b)
  
##複数個の整数の最小公倍数を求める
def lcm_multi(l) :
  if(len(l) < 2) :
    return l[0]
  res = lcm(l[0], l[1])
  for i in range(2, N) :
    res = lcm(l[i], res)
    
  return res

ans = 0
lcm_m = lcm_multi(list_a)

if(M-lcm_m/2 < 0) :
  print(0)
else :
  print(int((M-lcm_m/2) / lcm_m) + 1)


### FIXED CODE ###

N, M = list(map(int, input().split(" ")))
list_a = list(map(int, input().split(" ")))

##半公倍数が存在するかチェック
def check_exist(l) :
  if(len(l) == 1) :
    return True
  while(True) :
    flag = l[0] % 2
    for x in l[1:] :
      if(x % 2 != flag) :
        return False
    if(flag == 0) :
      l = list(map(lambda x: int(x/2), l))
    else :
      return True
    

##最大公約数を求める

def gcd(a, b) :
  if(b==0) :
    return a
  else :
    return gcd(b, a%b)
   
##最小公倍数を求める
def lcm(a, b) :
  cd = gcd(a, b)
  return (a / cd) * b
  
##複数個の整数の最小公倍数を求める
def lcm_multi(l) :
  cm = 1
  for x in l :
    cm = lcm(x, cm)
    if(cm > 4 * M) :
      print(0)
      exit()
    
  return cm

if(not(check_exist(list_a))) :
  print(0)
  exit()

## 1/2の公倍数
lcm_m = lcm_multi(list(map(lambda x: int(x/2), list_a)))

if(M-lcm_m < 0) :
  print(0)
else :
  print(int((M-lcm_m) / (2*lcm_m)) + 1)
import math
a=list[int(input()) for _ in range(5)]
x=0
y=0
for i in a:
  x+=math.ceil(i)
  if i%10>y:
    y=i%10
print(x+y-10)

### FIXED CODE ###

from math import ceil
a=[int(input()) for i in range(5)]
ans=10
sum=0
for i in a:
  x=(i-1)%10+1
  ans=min(ans,x)
  sum+=ceil(i/10)*10
if ans==10:
  print(sum)
else:
  print(sum+ans-10)
s=list(map(int,input().split()))
a=s[0]-[1]
if a>s[2]:
  print(0)
else:
  print(s[2]-a)

### FIXED CODE ###

s=list(map(int,input().split()))
s[0]=int(s[0])
s[1]=int(s[1])
s[2]=int(s[2])
a=0
if s[0]-s[1]>s[2]:
  print(0)
else:
  print(s[2]-s[0]+s[1])
def main():
    lst = input().split()
    stack = []
    for i in lst :
        if i == ""+"" :
            x = stack.pop()
            y = stack.pop()
            stack.append(x + y)

        elif i == "-" :
            x = stack.pop()
            y = stack.pop()
            stack.append(y - x)

        elif i == "*" :
            x = stack.pop()
            y = stack.pop()
            stack.append(x * y)

        else :
            stack.append(int(i))

    print(stack.pop())


if __name__ = "__main__" :
    main()

### FIXED CODE ###

def main() :
    lst = input().split()
    stack = []
    for i in lst :
        if i == "+" :
            x = stack.pop()
            y = stack.pop()
            stack.append(x + y)

        elif i == "-" :
            x = stack.pop()
            y = stack.pop()
            stack.append(y - x)

        elif i == "*" :
            x = stack.pop()
            y = stack.pop()
            stack.append(x * y)

        else :
            stack.append(int(i))

    print(stack.pop())


if __name__ == "__main__" :
    main()
# @author 

import sys

class EVirusTree2:

    def solve(self):
        from collections import defaultdict
        import sys
        sys.setrecursionlimit(10 ** 5 + 5)

        MOD = 10 ** 9 + 7
        n, k  = [int(_) for _ in input().split()]
        adj = {}
        for i in range(n - 1):
            a, b = [int(_) for _ in input().split()]
            a -= 1
            b -= 1
            if a in adj: adj[a].append(b)
            else: adj[a] = [b]
            a, b = b, a
            if a in adj: adj[a].append(b)
            else: adj[a] = [b]
        done = [0] * n
        def dfs(s, rem):
            done[s] = 1
            if rem < 0:
                return 0
            res = 1
            for x in adj[s]:
                if done[x]:
                    continue
                if rem <= 0:
                    return 0
                res = (res * rem) % MOD
                res = (res * dfs(x, k - 2)) % MOD
                rem -= 1
                if res == 0:
                    return 0
            return res

        print((dfs(0, k - 1) * k) % MOD)




solver = EVirusTree2()
input = sys.stdin.readline

solver.solve()


### FIXED CODE ###

# @author 

import sys

class EVirusTree2:

    def solve(self):
        from collections import defaultdict
        import sys
        sys.setrecursionlimit(10 ** 5 + 5)

        MOD = 10 ** 9 + 7
        n, k  = [int(_) for _ in input().split()]
        adj = defaultdict(list)
        for i in range(n - 1):
            a, b = [int(_) for _ in input().split()]
            a -= 1
            b -= 1
            adj[a].append(b)
            adj[b].append(a)
        done = [0] * n
        def dfs(s, rem):
            done[s] = 1
            if rem < 0:
                return 0
            res = 1
            for x in adj[s]:
                if done[x]:
                    continue
                if rem <= 0:
                    return 0
                res = (res * rem) % MOD
                res = (res * dfs(x, k - 2)) % MOD
                rem -= 1
                if res == 0:
                    return 0
            return res

        print((dfs(0, k - 1) * k) % MOD)




solver = EVirusTree2()
input = sys.stdin.readline

solver.solve()