Harryxun/stf_run huggingface dataset:
import sys

letter="abcdefghijklmnopqrstuvwxyz"
While True
    table=[0]*26
    try:
        input_str=input()
    except:
        break    
    for A in input_str:
        index=0
        for B in letter:
            if A == B or A == B.upper():
                table[index] += 1
                break
                index += 1

    for i in range(len(letter)):
        print("%s : %d"%(letter[i],table[i]))



### FIXED CODE ###

letter="abcdefghijklmnopqrstuvwxyz"
table=[0]*26
while True:
    try:
        input_str=input()
    except:
        break
    for A in input_str:
        index=0
        for B in letter:
            if A == B or A == B.upper():
                table[index] += 1
                break
            index += 1

for i in range(len(letter)):
    print("%s : %d"%(letter[i],table[i]))
import math

def func(x):
	if x <= 3:
		return {0:0,1:1,2:3,3:0}[x]
	
	nearest_bin = 2 ** int(math.log2(x))

	if ((x-nearest_bin + 1) %2) == 0:
		ans = 0
	else:
		ans = nearest_bin

	return nearest_bin ^ func(x - nearest_bin)


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

if A == B:
	print(A)
else:
	print(func(A-1)^func(B))

### FIXED CODE ###

import math

def get_nearest_bin(x):
	if x <= 1:
		return x
	y = x
	i=0
	while y !=0:
		y = y >> 1
		i += 1
	return (x >> (i-1) ) << (i-1)

def func(x):
	if x <= 3:
		return {0:0,1:1,2:3,3:0}[x]
	
	nearest_bin = get_nearest_bin(x)

	if ((x-nearest_bin + 1) %2) == 0:
		ans = 0
	else:
		ans = nearest_bin

	return ans ^ func(x - nearest_bin)


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

if A == B:
	print(A)

elif A == 0:
	print(func(B))
else:
	print(func(A-1)^func(B))
from collections import defaultdict, deque
import sys, heapq, bisect, math, itertools, string, queue, copy, time
from fractions import gcd
import numpy as np
sys.setrecursionlimit(10**8)
INF = float('inf')
MOD = 10**9+7
EPS = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())




N = int(input())
alist = list(map(int, input().split()))
ans_list = []

for i in range(N, 0, -1):
    if i > N//2:
        if alist[i-1]:
            ans_list.append(i)
    else:
        if sum(alist[i-1::i])%2 != alist[i-1]:
            ans_list.append(i)
print(len(ans_list))
if len(ans_list >0):
    print(*ans_list)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
 
b = [0] * n
 
for i in range(n, 0, -1):
    if sum(b[i-1::i]) % 2 == a[i-1]:
        continue
    else:
        b[i-1] = 1
 
c = []
for i in range(n):
    if b[i] == 1:
        c.append(i+1)
print(sum(b))
if len(c) > 0:
    print(*c)
n=int(input())
K=int(input())
if K==1:
    counter=0
    for i in range(100):
        for j in range(1,10):
            a="0"*(i)+str(j)+"0"*(99-i)
            if 1<=int(a)<=n:
                counter+=1
    print(counter)
elif K==2:
    counter=0
    for i in range(100):
        for j in range(i+1,100):
            for k in range(1,10):
                for l in range(1,10):
                    a="0"*(i)+str(k)+"0"*(j-i-1)+str(l)+"0"*(99-j)
                    if 1<=int(a)<=n:
                        counter+=1
    print(counter)
elif K==3:
    counter=0
    for i in range(100):
        if 100-i>len(str(n)):
            pass
        elif 100-i<len(str(n)):
            for j in range(i+1,100):
                for k in range(j+1,100):
                    counter+=9*9*9
        elif 100-i==len(str(n)):
            for j in range(i+1,100):
                for k in range(j+1,100):
                    for a in range(int(str(n)[i]),int(str(n)[i])+1):
                        for b in range(1,10):
                            for c in range(1,10):
                                P=str(a)+"0"*(j-i-1)+str(b)+"0"*(k-j-1)+str(c)+"0"*(99-k)
                                if 1<=int(P)<=n:
                                    counter+=1
            counter+=((98-i)*(99-i)//2)*9*9*(int(str(n)[i])-1)
    print(counter)
                    


                    


### FIXED CODE ###

n=int(input())
K=int(input())
if K==1:
    counter=0
    for i in range(100):
        for j in range(1,10):
            a="0"*(i)+str(j)+"0"*(99-i)
            if 1<=int(a)<=n:
                counter+=1
    print(counter)
elif K==2:
    counter=0
    for i in range(100):
        for j in range(i+1,100):
            for k in range(1,10):
                for l in range(1,10):
                    a="0"*(i)+str(k)+"0"*(j-i-1)+str(l)+"0"*(99-j)
                    if 1<=int(a)<=n:
                        counter+=1
    print(counter)
elif K==3:
    counter=0
    for i in range(100):
        if 100-i>len(str(n)):
            pass
        elif 100-i<len(str(n)):
            for j in range(i+1,100):
                for k in range(j+1,100):
                    counter+=9*9*9
        elif 100-i==len(str(n)):
            for j in range(i+1,100):
                for k in range(j+1,100):

                        for b in range(1,10):
                            for c in range(1,10):
                                P=(str(n)[0])+"0"*(j-i-1)+str(b)+"0"*(k-j-1)+str(c)+"0"*(99-k)
                                if 1<=int(P)<=n:
                                    counter+=1
            counter+=((98-i)*(99-i)//2)*9*9*(int(str(n)[0])-1)
    print(counter)
N , K = map(int,input().split())
S = str(input())
T =[] #０と１の個数を並べていったリスト
m = 1
for i in range(N-1):
    if S[i] == S[i + 1]:
        m = m + 1
    else:
        T.append(m)
        m = 1
T.append(m)
n = len(T)

left_1 = []
left_0 = []
if S[0] == str(1):
    if K >= (len(T) // 2):
        ans = N
    else:
        if len(T) % 2 == 0:
            i = 0
            while 2*i + 2*K + 1 <= n:
                left_1.append(sum(T[2*i:2*i+2*K+2]))
            left_1.append(sum(T[n - 2*K :n]))
            ans = max(left_1)
        else:
            i = 0
            while 2*i + 2*K + 1 <= n:
                left_1.append(sum(T[2*i:2*i+2*K+2]))
            ans = max(left_1)

else: # if S[0] == 0:
    if n % 2 == 0: 
        if K >= (len(T) / 2):
            ans = N
        else:
            left_0.append(sum(T[0:2*K]))
            i = 0
            while 2*i + 2*K + 2 <= n:
                left_1.append(sum(T[2*i + 1:2*i + 2*K + 3]))
            ans = max(left_0)
    
    else:
        if K >= (len(T)//2 + 1):
            ans = N
        else:
            left_0.append(sum(T[0:2*K]))
            left_0.append(sum(T[n-2*K:n]))
            while 2*i + 2*K + 2 <= n:
                left_1.append(sum(T[2*i + 1:2*i + 2*K + 3]))
            ans = max(left_0)

print (ans)
           


### FIXED CODE ###

A,B = map(int,input().split())
if  A > B:
    print(2*A-1)
elif A == B:
    print(2*A)
else:
    print(2*B-1)
x, y = list(input().split(" "))
if int(x, 16) > int(y, 16):
    print(">")
elif hex(x, 16) < hex(y, 16):
    print("<")
else:
    print("=")


### FIXED CODE ###

x, y = list(input().split())

if x > y:
  print(">")
elif x == y:
  print("=")
else:
  print("<")
#!/usr/bin/env python

def main(N, H):
    ans = 'Yes'

    min_val = H[0] -1
    for i in range(1, N):
        if min_val <= H[i] -1:
            min_val = H[i] -1
        elif min_val <= H[i]:
            min_val = H[i]
        else:
            ans = 'No'
            break
    return ans

if __name__ == '__main__':
    N = int(input())
    H = list(map(int, input().split()))
    print(main(N, H))


### FIXED CODE ###

#!/usr/bin/env python

def main(A, B, C):
    ans = C - (A - B)
    if ans > 0:
        return ans
    else:
        return 0

if __name__ == '__main__':
    A, B, C = list(map(int, input().split()))
    print(main(A, B, C))
from functools import reduce
import math

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

toshiList = list(map(int,input().split()))

absList =[0] * len(toshiList)

for i in range(0,len(toshiList)):
    absList[i] = abs( toshiList[i] - X)

ans = reduce(math.gcd,absList)
    
print(ans)

### FIXED CODE ###

# -*- coding: utf-8 -*-
import fractions
from functools import reduce

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

toshiList = list(map(int,input().split()))

absList =[0] * len(toshiList)

for i in range(0,len(toshiList)):
    absList[i] = abs( toshiList[i] - X)

ans = reduce(fractions.gcd,absList)
    
print(ans)
mass=int(input())
number=list(map(int,input().split()))

cnt = 0

for i in mass:
    if (i+1)%2!=0 and number[i]%2!=0:
        cnt+=1

print(cnt)


### FIXED CODE ###

mass=int(input())
number=list(map(int,input().split()))

cnt = 0

for i in range(mass):
    if (i+1)%2!=0 and number[i]%2!=0:
        cnt+=1

print(cnt)
import sys
a= str(input())
kaibun = list(a)
n = int(len(kaibun))
answer = "No"
strongn1 = int((n-1)/2)
strongn2 = int((n+3)/2)
for i in reversed(range((int((n+1)/2)),n)):
    if kaibun[i] == kaibun[n-i-1]:
        answer = "Yes"
    else:
        answer = "No"
        print(answer)
        sys.exit()
for i in range(int(strongn1/2)):
    if kaibun[i] == kaibun[strongn1-i-1]:
        answer = "Yes"
    else:
    	answer="No"
    	print(answer)
    	sys.exit()
for i in reversed(range(strongn2,n,int(strongn1/2))):
    if kaibun[i] == kaibun[strongn2-2-i+n]:
        answer = "Yes"
    else:
      	answer = "No"
print(answer)

### FIXED CODE ###

a= str(input())
kaibun = list(a)
n = int(len(kaibun))
answer = "No"
strongn1 = int((n-1)/2)
strongn2 = int((n+3)/2)
for i in reversed(range((int((n+1)/2)),n)):
    if kaibun[i] == kaibun[n-i-1]:
        answer = "Yes"
    else:
        answer = "No"
        break

if answer == "Yes":
    for i in range(int(strongn1/2)):

        if kaibun[i] == kaibun[strongn1-i-1]:
            answer = "Yes"
        else:
            answer="No"
            break
if answer == "Yes":
    for i in reversed(range(strongn2+int(strongn1/2)-1,n)):
        if kaibun[i] == kaibun[strongn2-2-i+n]:
            answer = "Yes"
        else:
            answer = "No"
            break
print(answer)
seen = [0,0,0,0,0,0,0,0,0]
seen[0],seen[1],seen[2] = (map(int,input().split()))
seen[3],seen[4],seen[5] = (map(int,input().split()))
seen[6],seen[7],seen[8] = (map(int,input().split()))
over = False
N = int(input())
for x in range(N):
  num = int(input())
  print(num)
  if num in seen:
    seen[x] = "O"
print(seen)
if seen[0] == "O":
  if seen[1] == seen[2] == "O":
    print("YES")
    over = True
  elif seen[3] == seen[6] == "O":
    print("YES")
    over = True
  elif seen[4] == seen[8] == "O":
    print("YES")
    over = True
elif seen[4] == "O":
  if seen[2] == seen[6] == "O":
    print("YES")
    over = True
  elif seen[1] == seen[7] == "O":
    print("YES")
    over = True
  elif seen[3] == seen[5] == "O":
    print("YES")
    over = True
elif seen[8] == "O":
  if seen[6] == seen[7] == "O":
    print("YES")
  if seen[2] == seen[5] == "O":
    print("YES")
  over = True
if not over:
  print("NO")

### FIXED CODE ###

seen = [0,0,0,0,0,0,0,0,0]
seen[0],seen[1],seen[2] = (map(int,input().split()))
seen[3],seen[4],seen[5] = (map(int,input().split()))
seen[6],seen[7],seen[8] = (map(int,input().split()))
over = "No"
N = int(input())
for x in range(N):
  num = int(input())
  if num in seen:
    seen[seen.index(num)] = "O"
if seen[0] == "O":
  if seen[1] == "O" and seen[2] == "O":
    over = "Yes"
  if seen[3] == "O" and seen[6] == "O":
    over = "Yes"
  if seen[4] == "O" and seen[8] == "O":
    over = "Yes"
if seen[8] == "O":
  if seen[6] == "O" and seen[7] == "O":
    over = "Yes"
  if seen[2] == "O" and seen[5] == "O":
    over = "Yes"
if seen[4] == "O":
  if seen[6] == "O" and seen[2] == "O":
    over = "Yes"
  if seen[1] == "O" and seen[7] == "O":
    over = "Yes"
  if seen[3] == "O" and seen[5] == "O":
    over = "Yes"
print(over)
# -*- coding: utf-8 -*-

A = map(int, input())
B = map(int, input())
if A > B:
    print('GREATER')
elif A < B:
    print('LESS')
else:
    print('EQUAL')

### FIXED CODE ###

# -*- coding: utf-8 -*-

A = input()
B = input()
if len(A) > len(B):
    print('GREATER')
elif len(A) < len(B):
    print('LESS')
else:
    for i in range(len(A)):
        if A[i] > B[i]:
            print('GREATER')
            exit()
        elif A[i] < B[i]:
            print('LESS')
            exit()
        else:
            continue
    print('EQUAL')
#m-solutions2020 c
import sys,
input = sys.stdin.readline

N,K = list(map(int,input().split()))
A = list(map(int,input().split()))
for i in range(K,N):
    if A[i]>A[i-K]:
        print('Yes')
    else:
        print('No')



### FIXED CODE ###

#m-solutions2020 c
import sys
input = sys.stdin.readline


N,K = list(map(int,input().split()))
A = list(map(int,input().split()))
for i in range(K,N):
    if A[i]>A[i-K]:
        print('Yes')
    else:
        print('No')
#coding: shift_jis


N = int(raw_input())
S = raw_input()
x = 0
y = [x]
for i in range(N):
    if S[i] == 'I':
        x += 1
    elif S[i] == 'D':
        x -= 1
    y.append(x)
print max(y)



    



  
    
    

    
    
#coding: shift_jis


N = int(raw_input())
S = raw_input()
x = 0
y = [x]
for i in range(N):
    if S[i] == 'I':
        x += 1
    elif S[i] == 'D':
        x -= 1
    y.append(x)
print max(y)



  

### FIXED CODE ###

#coding: shift_jis


N = int(raw_input())
S = raw_input()
x = 0
y = [x]
for i in range(N):
    if S[i] == 'I':
        x += 1
    elif S[i] == 'D':
        x -= 1
    y.append(x)
print max(y)
import sys
N, Q = [int(i) for i in input().split()]
tree = {i:[] for i in range(N)}
cost_ls = {i:0 for i in range(N)}
for i in range(N-1):
    a, b = [int(j) for j in sys.stdin.readline().split()]
    a -= 1
    b -= 1
    tree[a].append(b)
    tree[b].append(a)

yet = set()
def plus(node, num):
    yet.add(node)
    cost_ls[0] += num
    if len(tree[node]) > 0:
        for child in tree[node]:
            if child in yet:
                continue
            plus(child, cost_ls[0])

for i in range(Q):
    p, x = [int(j) for j in sys.stdin.readline().split()]
    cost_ls[p-1] += x

plus(0, 0)

print(" ".join([str(cost) for cost in cost_ls]))

### FIXED CODE ###

import sys

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

N, Q = map(int, input().split())
V = {i: [] for i in range(1, N + 1)}
for _ in range(N - 1):
    a, b = map(int, input().split())
    V[a].append(b)
    V[b].append(a)

C = {i: 0 for i in range(1, N + 1)}

for _ in range(Q):
    p, x = map(int, input().split())
    C[p] += x


def propagate(u, p):
    for v in V[u]:
        if v == p:
            continue
        C[v] += C[u]
        propagate(v, u)


propagate(1, 0)

print(' '.join(str(C[i]) for i in range(1, N + 1)))
n = int(input())
seq = list(map(int, input().split()))
q = int(input())
mlist = list(map(int, input().split()))

def check(i, m):
    if m == 0:
        return True
    elif i >= n:
        return False
    res = check(i+1, m) + check(i+1, m - seq[i])
    return res

for m in mlist:
    if(check(0,m)):
        print('yes')
    else:
        print('no')


### FIXED CODE ###

n = int(input())
seq = list(map(int, input().split()))
q = int(input())
mlist = list(map(int, input().split()))
mins = min(seq)
sums = 0
for a in seq:
    sums += a

def check(i, m):
    global mins
    if m == 0:
        return True
    elif i >= n or mins > m:
        return False
    res = check(i+1, m) or check(i+1, m - seq[i])
    return res

for m in mlist:
    if (mins > m or sums < m):
        print('no')
    elif(check(0,m)):
        print('yes')
    else:
        print('no')
N=int(input())

if N<=9:
    print(N)
elif N<=99:
    print(9)
elif N<=999:
    X=9+(N-99)
    print(X)
elif N<=9999:
    print(909)
elif N<=99999:
    X=909+(N-9999)
    print(x)
else:
    print(90909)

### FIXED CODE ###

N=int(input())

if N<10:
    print(N)
elif N<100:
    print(9)
elif N<1000:
    X=9+(N-99)
    print(X)
elif N<10000:
    print(909)
elif N<100000:
    X=909+(N-9999)
    print(X)
else:
    print(90909)
S = int(input())
print('Heisei' if S[5]==0 and S[6]<5 else 'TBD')    

### FIXED CODE ###

S = list(str(input()))
print('Heisei' if int(S[5])==0 and int(S[6])<5 else 'TBD')
a, b = map(str, input().split())
n = 0
for i in range(2):
  if a[i] == b[i]:
    n += 1
print(n)

### FIXED CODE ###

a = input()
b = input()
n = 0
for i in range(3):
  if a[i] == b[i]:
    n += 1
print(n)
A, B, C, D, E, F = map(int, input().split())

#memo
list = [0, 0]

#操作1-4
ope1 = 100 * A
ope2 = 100 * B
ope3 = C
ope4 = D
#入れた水、砂糖の総量
w_sum = 0
s_sum = 0
#パーセンテージ
p = 0
#トータル
total = w_sum + s_sum
#砂糖の表示用の変数
s = 0

for i in range(101):
    for j in range(101):
        for k in range(31):
            for l in range(31):
                w_sum = l * ope1 + k * ope2
                s_sum = j * ope3 + i * ope4
                if w_sum != 0 and w_sum + s_sum <= F and s_sum <= E * (l + k) :
                    p_tmp = (s_sum / (w_sum + s_sum)) * 100
                    if p_tmp >= p:
                        p = p_tmp
                        list[0] = w_sum + s_sum
                        list[1] = s_sum

print(list[0], list[1])                        


### FIXED CODE ###

N = int(input())                                                                                                                                            
A = int(input())
  
ans = (N * N) - A
  
print(str(ans))
import sys
def euc(li):
    if (li[0] == 0 or li[1] == 0):
        return li[1]
    return euc((li[0]-li[1],li[1]) if li[0]>li[1] else (li[1]-li[0],li[0]))
for line in sys.stdin:
    [a,b] = [int(x) for x in line.split()]
    gcd = euc([a,b])
    print gcd,a*b/gcd

### FIXED CODE ###

import sys
def gcd(a,b):
    if (b == 0):
        return a
    return gcd(b,a%b)
for line in sys.stdin:
    a,b = [int(x) for x in line.split()]
    d = gcd(a,b)
    print d,a*b/d
import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 5 + 5)


def dfs(v, p, ccc, links, ans):
    ret_colors = defaultdict(int)
    ret_count = 1
    cv = ccc[v]
    for u in links[v]:
        if u == p:
            continue
        sub_colors, sub_count = dfs(u, v, ccc, links, ans)
        cc = sub_count - sub_colors[cv]
        ans[cv] -= cc * (cc + 1) // 2
        ret_count += sub_count

        if len(ret_colors) < len(sub_colors):
            ret_colors, sub_colors = sub_colors, ret_colors

        for c, cnt in sub_colors.items():
            ret_colors[c] += cnt

    ret_colors[cv] = ret_count

    return ret_colors, ret_count


def solve(n, ccc, links):
    if n == 1:
        return [1]

    all_pair = n * (n + 1) // 2
    ans = [all_pair] * (n + 1)

    colors, count = dfs(0, -1, ccc, links, ans)
    assert count == n

    for c in range(1, n + 1):
        cc = n - colors[c]
        ans[c] -= cc * (cc + 1) // 2

    return ans[1:]


n, *cab = map(int, sys.stdin.buffer.read().split())
ccc = cab[:n]
links = [set() for _ in range(n)]

for a, b in zip(cab[n + 0::2], cab[n + 1::2]):
    a -= 1
    b -= 1
    links[a].add(b)
    links[b].add(a)

print('\n'.join(map(str, solve(n, ccc, links))))


### FIXED CODE ###

import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 6)


def dfs(v, p, ccc, links, ans):
    ret_colors = defaultdict(int)
    ret_count = 1
    cv = ccc[v]
    for u in links[v]:
        if u == p:
            continue
        sub_colors, sub_count = dfs(u, v, ccc, links, ans)
        cc = sub_count - sub_colors[cv]
        ans[cv] -= cc * (cc + 1) // 2
        ret_count += sub_count

        if len(ret_colors) < len(sub_colors):
            ret_colors, sub_colors = sub_colors, ret_colors

        for c, cnt in sub_colors.items():
            ret_colors[c] += cnt

    ret_colors[cv] = ret_count

    return ret_colors, ret_count


def solve(n, ccc, links):
    if n == 1:
        return [1]

    all_pair = n * (n + 1) // 2
    ans = [all_pair] * (n + 1)

    colors, count = dfs(0, -1, ccc, links, ans)
    assert count == n

    for c in range(1, n + 1):
        cc = n - colors[c]
        ans[c] -= cc * (cc + 1) // 2

    return ans[1:]


n, *cab = map(int, sys.stdin.buffer.read().split())
ccc = cab[:n]
links = [set() for _ in range(n)]

for a, b in zip(cab[n + 0::2], cab[n + 1::2]):
    a -= 1
    b -= 1
    links[a].add(b)
    links[b].add(a)

print('\n'.join(map(str, solve(n, ccc, links))))
S = input().split()
 
print(sum(S))

### FIXED CODE ###

S,T = input().split()
print(T+S)
w,h,n=map(int,input().split())
mat=[[1]*h for _ in range(w)]
print(mat)
l=[-1]*5
l[2]=float('inf')
l[4]=float('inf')
for _ in range(n):
    x,y,a=map(int,input().split())
    if a==1:
        l[1]=max(l[1],x)
    elif a==2:
        l[2]=min(l[2],x)
    elif a==3:
        l[3]=max(l[3],y)
    else:
        l[4]=min(l[4],y)
for i in range(h):
    for j in range(w):
        if l[1]!=-1:
            if i<



### FIXED CODE ###

a,b,c=map(int,input().split())
for k in range(1,b+1):
    if (k*a)%b==c%b:
        print('YES')
        import sys
        sys.exit()
print('NO')
class Node:
    def __init__(self):
        self.next=[]
    def get_data(self,new_next,weight=1):
        self.next.append({new_next:weight})
def BFS(i,depth,K):  
    depth+=1
    tmp=[list(j.keys())[0] for j in i]
    if depth==0:
        seki=K
    else:
        if depth==1:
            calc=K-1
            diff=0
        else:
            calc=K-2
            diff=1
        seki=1
        if (len(tmp))>1 or depth<2:
            for i in range(calc,max(1,calc-(len(tmp)-diff)),-1):
                seki*=i
            
    for each in tmp:
        if not check_node[each]:
            check_node[each]=True
            
            seki*=BFS(node[each].next,depth,K)
    return seki


N,K=list(map(int,input().split()))
node=[Node() for _ in range(N)]
check_node=[False for _ in range(N)]
check_node[0]=True
for i in range(N-1):
    p,n=list(map(int,input().split()))
    node[n-1].get_data(p-1)
    node[p-1].get_data(n-1)
start=0
d=0

com=K*BFS(node[0].next,d,K)
print(com%1000000007)

### FIXED CODE ###

import sys
import math
sys.setrecursionlimit(1000000)
mod=1000000007
class Node:
    def __init__(self):
        self.next=[]
    def get_data(self,new_next,weight=1):
        self.next.append(new_next)
def BFS(i,depth,K):  
    depth+=1
    tmp=i
    seki=1
    num=len(tmp)
    if depth==1:
        calc=K-1
        loop=range(calc,calc-num,-1)
        for i in loop:
            seki*=i%1000000007

        
    else:
        calc=K-2
        num-=1
        if calc>=num:
            seki=cache[num]
        else:
            print(0)
            exit()

            
            
    for each in tmp:
        if not check_node[each]:
            check_node[each]=True
            seki*=BFS(node[each].next,depth,K)%mod
    return seki


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

if K>2:
    cache=[0 for i in range(K-2)]
    cache[0]=1
    for i in range(1,K-2):
        cache[i]=cache[i-1]*(K-1-i)%mod
    cache.append(cache[-1])
else:
    cache=[1,1]
node=[Node() for _ in range(N)]
check_node=[False for _ in range(N)]
check_node[0]=True
for i in range(N-1):
    p,n=list(map(int,input().split()))
    node[n-1].get_data(p-1)
    node[p-1].get_data(n-1)
start=0
d=0

com=K*BFS(node[0].next,d,K)
print(int(com)%mod)
n = int(input())
ans =0

for i in range(1,n):
    ans +=(n-1)//a
print(ans)

### FIXED CODE ###

n = int(input())
ans =0

for i in range(1,n):
    ans +=(n-1)//i
print(ans)