Harryxun/stf_run huggingface dataset:
if input().find("9")>-1:
  print("Yes")
 else:
    print("No")


### FIXED CODE ###

if input().find('9')>-1:
  print("Yes")
else:
    print("No")
#coding: utf-8

line = input()
for i in range(3):
	arr.append(int(line.split()[i]))
ans = sum(arr) - max(arr)
print(ans)



### FIXED CODE ###

#coding: utf-8

line = input()
arr = []
for i in range(3):
	arr.append(int(line.split()[i]))
ans = sum(arr) - max(arr)
print(ans)
n, m = map(int, input().split())
an = [0]*m

for i in range(m):
#    s = input()
    an[i] = int( input() )
#an[-1] = n

#an.sort()
disjoint = False
for i in range(len(an)-1):
    if an[i] + 1 == an[i+1]:
        disjoint = True





if disjoint:
    print(0)

else:

    mod = 10**9+7
    tab = [0]*(10**5+1)
    tab[0] = 0
    tab[1] = tab[2]= 1

    for i in range(3, len(tab)):
        tab[i] = tab[i-1]+tab[i-2]
#        if i<100:
#            print(tab[i])

    an.append(n)
    prev = 0
    ans = 1
    for a in an:
        index = a-prev + (1 if a == n else 0)
        print(a,prev,index,tab[index])
        ans *= tab[index]
        ans %= mod
        prev = a+1

    #ans *= tab[n - prev]
    #ans %= 1000000007

    print(ans)



### FIXED CODE ###

n, m = map(int, input().split())
an = [0]*m

for i in range(m):
#    s = input()
    an[i] = int( input() )
#an[-1] = n

#an.sort()
disjoint = False
for i in range(len(an)-1):
    if an[i] + 1 == an[i+1]:
        disjoint = True


if disjoint:
    print(0)

else:

    mod = 10**9+7
    tab = [0]*(10**5+10)
    tab[0] = 0
    tab[1] = tab[2]= 1

    for i in range(3, len(tab)):
        tab[i] = tab[i-1]+tab[i-2]
#        if i<100:
#            print(tab[i])

    an.append(n)
    prev = 0
    ans = 1
    for a in an:
        index = a-prev + (1 if a == n else 0)
#        print(a,prev,index,tab[index])
        ans *= tab[index]
        ans %= mod
        prev = a+1

    #ans *= tab[n - prev]
    #ans %= 1000000007

    print(ans)
N = int(input())
A = []
for i in range(N):
    S, P = map(str, input().split())
    P = int(p)
    A.append([S, -P])
A.sort()
for i in A:
    print(A.index(i)+1)


### FIXED CODE ###

N = int(input())
A = []
for i in range(N):
    S, P = map(str, input().split())
    P = int(P)
    A.append([S, -P])
S = sorted(A)
for j in S:
    print(A.index(j) + 1)
# -*- coding: utf-8 -*-
"""
Created on Sat May  2 14:48:19 2020

@author: ab
"""
import math
import sys
import os

def isDivisible(num1,num2):
    return num1%num2 == 0

def binary_search(n,m,k):
    if isDivisible(n,k) | isDivisible(m,k):
        return True
    elif abs(n-m) <=1:
        return False
    mid = math.ceil((n+m)/2)
    if(isDivisible(mid,k)):
        return True
    elif mid-n < k:
        return binary_search(mid+1,m,k)
    else:
        return binary_search(n,mid-1,k)
    

def solution(k,n,m):
    if k == 1:
        return True
    elif isDivisible(n,k) | isDivisible(m,k):
        return True
    elif abs(n-m) <=1:
        return False
    elif k>m:
        return False
    else:
        return binary_search(n,m,k)



input = sys.stdin
output = sys.stdout
while True:
    lineElements = input.readline().rstrip("/n").split(" ")
    if(lineElements[0] == ''):
        break;
    if len(lineElements) == 1:
        k = int(lineElements[0])
    else:
        n,m = lineElements
        n,m = int(n),int(m)
        if solution(k,n,m) == True:
            output.writeLine("OK")
        else:
            output.writeLine("NG")


### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sat May  2 14:48:19 2020

@author: ab
"""
# import math
import sys
# import os

def isDivisible(num1,num2):
    return num1%num2 == 0

def search(n,m,k):
    if isDivisible(n,k) | isDivisible(m,k):
        return True
    elif abs(n-m) <=1:
        return False
    for i in range(n,m):
        if isDivisible(i, k):
            return True
    return False
    
def solution(k,n,m):
    if k == 1:
        return True
    elif isDivisible(n,k) | isDivisible(m,k):
        return True
    elif abs(n-m) <=1:
        return False
    elif k>m:
        return False
    else:
        return search(n,m,k)



input = sys.stdin
output = sys.stdout
while True:
    lineElements = input.readline().rstrip("/n").split(" ")
    if(lineElements[0] == ''):
        break;
    if len(lineElements) == 1:
        k = int(lineElements[0])
    else:
        n,m = lineElements
        n,m = int(n),int(m)
        if solution(k,n,m) == True:
            print("OK\n")
        else:
            print("NG\n")
# output.flush()
k = int(input())
a,b = map(int,input())
d = 0	
for i in range(a,b+1):
  if i%k == 0:
    d = 3
    break
  else:
    d=0
if d == 3:
  print('OK')
else:
  print('NG')

### FIXED CODE ###

k = int(input())
a,b=map(int,input().split())
count = 0
for i in range(a,b+1):
    if i%k == 0:
        count += 1
if count == 0:
    print("NG")
else:
    print("OK")
S = input()


def solve():
    # print(S)
    diff = ord("a")

    head = 0
    while head < len(S):
        tail = head + 1
        while tail <= len(S):
            # print(S[head:tail])
            table = [0 for _ in range(abs(ord("z") - ord("a")))]
            for j in range(len(S[head:tail])):
                # print("\t{}".format(S[head:tail][j:j+1]))
                index = ord(S[head:tail][j:j+1]) - diff
                table[index] += 1
                # print(table[index], len(S[head:tail]), table[index] / len(S[head:tail]))
                if len(S[head:tail]) >= 2 and table[index] / len(S[head:tail]) > 0.5:
                    # print("hit:" + S[head:tail])
                    # print(head + 1, tail)
                    return head + 1, tail

            tail += 1
        head += 1

    # print("no hit")
    return -1, -1

res = solve()
print(res[0], res[1])


### FIXED CODE ###

S = input()

def solve2():
    head = 0
    tail = 2
    while head < len(S):
        # print(S[head:tail])
        # print("\t" + S[head:tail][0:1])
        # print("\t" + S[head:tail][1:2])
        if S[head:tail][0:1] == S[head:tail][1:2]:
            return head + 1, tail
        head += 1
        tail += 1

    head = 0
    tail = 3
    while head < len(S):
        # print(S[head:tail])
        # print("\t" + S[head:tail][0:1])
        # print("\t" + S[head:tail][1:2])
        # print("\t" + S[head:tail][2:3])
        if S[head:tail][0:1] == S[head:tail][2:3]:
            return head + 1, tail
        head += 1
        tail += 1

    return -1, -1

res = solve2()
print(res[0], res[1])
print(r*r)

### FIXED CODE ###

r=int(input())
print(r*r)
li = [int(x) for x in input().split()]
li.sort()
li.reversed()
if(li[0]==li[1]+li[2]):
  print('Yes')
else:
  print('No')

### FIXED CODE ###

li = [int(x) for x in input().split()]
li.sort()
li.reverse()
if(li[0]==li[1]+li[2]):
  print('Yes')
else:
  print('No')
def permutation(lst): 
    # If lst is empty then there are no permutations 
	if len(lst) == 0: 
		return [] 
  
    # If there is only one element in lst then, only 
    # one permuatation is possible 
	if len(lst) == 1: 
		return [lst] 
  
    # Find the permutations for lst if there are 
    # more than 1 characters 
  
    l = [] # empty list that will store current permutation 
  
    # Iterate the input(lst) and calculate the permutation 
    for i in range(len(lst)): 
       m = lst[i] 
  
       # Extract lst[i] or m from the list.  remLst is 
       # remaining list 
       remLst = lst[:i] + lst[i+1:] 
  
       # Generating all permutations where m is first 
       # element 
       for p in permutation(remLst): 
           l.append([m] + p) 
    return l 
 
N = input()
x = [int(x) for x in input().split()]
y = [int(x) for x in input().split()]
 
NN = list(range(1,int(N)+1))
P = permutation(NN)
 
xx = P.index(x)
yy = P.index(y)
print(abs(xx-yy))

### FIXED CODE ###

def permutation(lst):
    # If lst is empty then there are no permutations
  if len(lst) == 0:
    return []

        # If there is only one element in lst then, only
    # one permuatation is possible
  if len(lst) == 1:
    return [lst]

        # Find the permutations for lst if there are
    # more than 1 characters

  l = []  # empty list that will store current permutation

    # Iterate the input(lst) and calculate the permutation
  for i in range(len(lst)):
    m = lst[i]

        # Extract lst[i] or m from the list.  remLst is
        # remaining list
    remLst = lst[:i] + lst[i + 1:]

        # Generating all permutations where m is first
        # element
    for p in permutation(remLst):
      l.append([m] + p)
  return l


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

NN = list(range(1, int(N) + 1))
P = permutation(NN)

xx = P.index(x)
yy = P.index(y)
print(abs(xx - yy))
#!/usr/bin/env python3
import sys
import numpy as np
sys.setrecursionlimit(10 ** 7)

MOD = 2  # type: int


def solve(N: int, a: "List[int]"):
    a = np.array(a)
    ans = np.zeros(N)
    # print(ans)
    ans_idx = []
    for i in range(N - 1, -1, -1):
        # print(i)
        # print(list(range(i * 2 + 1, N, i + 1)))
        # print(ans[range(i * 2 + 1, N, i + 1)])
        # print()
        if (a[i] + ans[range(i * 2 + 1, N, i + 1)].sum()) % 2 == 0:
            ans[i] = 0
        else:
            ans[i] = 1
            ans_idx.append(i + 1)
    # print(ans)
    b = int(sum(ans))
    print(b)
    if b:
        print(*ans_idx)
    return


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools
# (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, a)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10 ** 7)

MOD = 2  # type: int


def solve(N: int, a: "List[int]"):
    ans = [0 for x in range(N)]
    for i in range(N - 1, -1, -1):
        s = 0
        for j in range(i, N, i + 1):
            s += ans[j]
        # print(s, a[i], s ^ a[i])
        if (s + a[i]) & 1:
            ans[i] = 1
    # print(ans)
    b = int(sum(ans))
    print(b)
    l = []
    if b:
        for i, x in enumerate(ans):
            if x == 1:
                l.append(i + 1)
        print(*l)
    return


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools
# (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, a)


if __name__ == '__main__':
    main()
import math
from fractions import gcd

a,b = map(int,input().split())
gcr = gcd(a,b)
is_p = [True] * (gcr+1)
is_p[0] = False
for i in range(2, gcr+1):
    if is_p[i]:
        for j in range(2*i, gcr+1, i):
            is_p[j] = False

ps = [i for i, v in enumerate(is_p) if v and gcr % i == 0]
print(len(ps))




### FIXED CODE ###

import math
from fractions import gcd

a,b = map(int,input().split())
g = gcd(a,b)
gr = int(math.ceil(math.sqrt(g)))

facs = [1]
i = 2
while i*i <= g:
    if g == 1:
        break
    if g % i == 0:
        facs.append(i)
        while g % i == 0:
            g //= i
    i += 1
if g != 1:
    facs.append(g)

print(len(facs))
import itertools
import math
import string
import collections
from collections import Counter
from collections import deque
from operator import itemgetter
import sys
sys.setrecursionlimit(2*10**5)
INF = 2**60


def readints():
    return list(map(int, input().split()))


def nCr(n, r):
    return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))


def has_duplicates2(seq):
    seen = []
    for item in seq:
        if not(item in seen):
            seen.append(item)
    return len(seq) != len(seen)


def divisor(n):
    divisor = []
    for i in range(1, n+1):
        if n % i == 0:
            divisor.append(i)
    return divisor


# coordinates
dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]
a, b, c, d = map(int, input().split())


def func(n, c, d):
    x = n//c
    y = n//d
    z = n//((c * d) // math.gcd(c, d))
    zz = (x+y)-z
    return zz


tmp = b-func(b, c, d)
tmp2 = (a-1)-func(a-1, c, d)
print(tmp-tmp2)
#print('test', func(6, 2, 3))


### FIXED CODE ###

import itertools
import math
import fractions
import string
import collections
from collections import Counter
from collections import deque
from operator import itemgetter
import sys
sys.setrecursionlimit(2*10**5)
INF = 2**60


def readints():
    return list(map(int, input().split()))


def nCr(n, r):
    return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))


def has_duplicates2(seq):
    seen = []
    for item in seq:
        if not(item in seen):
            seen.append(item)
    return len(seq) != len(seen)


def divisor(n):
    divisor = []
    for i in range(1, n+1):
        if n % i == 0:
            divisor.append(i)
    return divisor


# coordinates
dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]
a, b, c, d = map(int, input().split())


def func(n, c, d):
    x = n//c
    y = n//d
    z = n//((c * d) // fractions.gcd(c, d))
    zz = (x+y)-z
    return zz


tmp = b-func(b, c, d)
tmp2 = (a-1)-func(a-1, c, d)
print(tmp-tmp2)
#print('test', func(6, 2, 3))
n,m=map(int,input().split())
a=[]
for i in range(m):
    a.append(int(input()))
count=[0]*(n+2)
count[1]=2
count[0]=1
i=0
s=a.pop(0)
if s==1:
    count[1]=1
    count[0]=0
    if a:
        s=a.pop(0)
if s==2:
    count[1]=0
    if a:
        s=a.pop(0)

while i<n:        
    if (i+2==s-1):
        i=i+1
        if a:
            s=a.pop(0)
    else:
        count[i+2]=(count[i]+count[i+1])%1000000007
        i=i+1
#print(count)
print(count[n-1])


### FIXED CODE ###

n,m=map(int,input().split())
a=[]
for i in range(m):
    x=int(input())
    if a:
        if x!=a[-1]:
            a.append(x)
    else:
        a.append(x)
count=[0]*(n+2)
count[1]=2
count[0]=1
i=0
s=0
if a:
    s=a.pop(0)
if s==1:
    count[1]=1
    count[0]=0
    if a:
        s=a.pop(0)
if s==2:
    count[1]=0
    if a:
        s=a.pop(0)

while i<n:        
    if (i+2==s-1):
        i=i+1
        if a:
            s=a.pop(0)
    else:
        count[i+2]=(count[i]+count[i+1])%1000000007
        i=i+1
#print(count)
print(count[n-1])
from fractions import gcd

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


def cnt_div(a, b, x):
    q, r = divmod(a, x)

    if r == 0:
        m = q - 1
    else:
        m = q

    n = b // x

    return n - m


num_c = cnt_div(a, b, c)
num_d = cnt_div(a, b, d)
lcm = int((c * d) / gcd(c, d))
num_c_d_gcd = cnt_div(a, b, lcm)

print((b - a + 1) - (num_c + num_d - num_c_d_gcd))


### FIXED CODE ###

S = input()

l = len(S)

for i in range(1, l):
    if S[i - 1] == S[i]:
        print("Bad")
        break
    else:
        if i == l - 1:
            print("Good")
            break
        else:
            continue
N, M = map(int, input().split())
sc = [list(map(int, input().split())) for _ in range(M)]

ok = False
n = [-1] * M
for s, c in sc:
  if n[s-1] != -1:
    if n[s-1] == c: continue
    ans = -1
    ok = True
    break
  n[s-1] = c

if n[0] == 0:
  ans = -1
  ok = True
if not ok:
  ans = ""
  for i in range(M):
    if i == 0 and n[i] == -1:
      ans += "1"
    elif n[i] == -1:
      ans += "0"
    else:
      ans += str(n[i])
print(ans)

### FIXED CODE ###

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

ans = ["0"] * N
if N > 1: ans[0] = "1"
rep = {}

ok = True
for s, c in sc:
  ans[s - 1] = str(c)
  if s in rep and rep[s] != str(c):
    ok = False
  else:
    rep[s] = str(c)

if ok:
  if ans[0] == "0" and N > 1:
    ok = False

print("".join(ans) if ok else -1)
import fractions
n = int(input())
l = list(map(int,input().split()))

ans = l[0]*l[1]/fractions.gcd(l[0],l[1])
for i in range(2,n):
    ans = ans*l[i]/fractions.gcd(ans,l[i])

mod = 10**9+7
a = 0
for i in range(n):
    a += ans//l[i]
    a %= mod
print(int(a%mod))


### FIXED CODE ###

import fractions
n = int(input())
l = list(map(int,input().split()))
if n == 1:
    print(1)
    exit()

def lcm(a,b):
    return a*b//fractions.gcd(a,b)
ans = l[0]
for i in range(1,n):
    ans = lcm(ans,l[i])
    

mod = 10**9+7
a = 0
for i in range(n):
    a += ans//l[i]
    
print(a%mod)
n,m = list(map(int,input().split()))
a = [0]*m
for i in range(m):
    a[i] = int(input())

def stair(k):
    if k == 1:
        if 1 not in a:
            return 1
        else:
            return 0
    elif k == 2:
        if 2 not in a:
            return 1 + stair(1)
        else:
            return 0 + stair(1)
    if k not in a:
        if k-1 not in a:
            if k-2 not in a:
                return (stair(k-1)+stair(k-2))%1000000007
            else:
                return stair(k-1)
        else:
            if k-2 not in a:
                return stair(k-2)
            else:
                return 0
    else:
        return 0

print(stair(n))

### FIXED CODE ###

n,m = list(map(int,input().split()))
a = [0]*m
for i in range(m):
    a[i] = int(input())
dp = [0]*(n+2)
for i in a:
    dp[i] = -1
dp[0] = 1

for i in range(n):
    if dp[i]<0:
        continue
    dp[i] %= 10**9+7
    if dp[i+1]>=0:
        dp[i+1] += dp[i]
    if dp[i+2]>=0:
        dp[i+2] += dp[i]
print(dp[n]%(10**9+7))
N,K = map(int, input().split())
L = []
for i in range(N):
  d = int(input())
  if d == 1:
    A = list(int(input()))
  else:
    A = list(map(int, input().split()))
  for j in range(d):
    L.append(A[j])
print(N-len(set(L)))


### FIXED CODE ###

N,K = map(int, input().split())
L = []
for i in range(K):
  d = int(input())
  A = list(map(int, input().split()))
  for j in range(d):
    L.append(A[j])
print(N-len(set(L)))
n, k = map(int, input().split())
arr = list(map(int, input().split()))

# n, k = 4, 5
# arr = list(map(int, "10 1 2 22".split()))

add = sum(arr)

def check(factor):
	mod_factor = [x%factor for x in arr]
	left, right = 0, n-1
	reqd, rem = 0, 0
	mod_factor.sort()
	counter = 0
	while left <= right:
		reqd = factor - mod_factor[right]
		while mod_factor[right]% factor != 0:
			if reqd < mod_factor[left]:
				mod_factor[left] -= reqd
				mod_factor[right] = 0
				counter += reqd
			else:
				mod_factor[right] -= mod_factor[left]
				reqd -= mod_factor[left]
				counter += mod_factor[left]
				left += 1
		right -= 1
	return countera <= k

ans = i = 1
while i*i <= add:
	if add % i == 0:
		if check(i):
			ans = max(ans, i)
		if check(add//i):
			ans = max(ans, add//i)
	i += 1
print(ans)

### FIXED CODE ###

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

# n, k = 8, 7
# arr = list(map(int, "1 7 5 6 8 2 6 5".split()))

add = sum(arr)

def check(factor):
	mod_factor = [x%factor for x in arr]
	mod_factor.sort(reverse = True)
	p = sum(mod_factor)//factor
	# print('p: ', p, 'factor:',factor, 'sum: ', sum(mod_factor))
	# print('mod_factor: ', mod_factor)
	# print(mod_factor[:p])
	c = sum(factor - mod_factor[i] for i in range(p))
	return c <= k

ans = i = 1
while i*i <= add:
	if add % i == 0:
		if check(i):
			ans = max(ans, i)
		if check(add//i):
			ans = max(ans, add//i)
	i += 1
print(ans)
n = int(input())
a,b,c = list(map(int, input().split()))
ma=sum(b)
for i in range(0,n-1):
    if a[i+1]-a[i]==1:
        ma+=c[a[i]-1]
print(ma)

### FIXED CODE ###

n = int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
ma=sum(b)
for i in range(0,n-1):
    if a[i+1]-a[i]==1:
        ma+=c[a[i]-1]
print(ma)
S = int(input())
print(S)

### FIXED CODE ###

S = list(input())
Ss = set(S)
count2 = 0
for alp in Ss:
    if S.count(alp) == 2:
        count2 += 1
if count2 == len(Ss):
    print("Yes")
else:
    print("No")
n = int(input())
arr = input().split()
ans = []
for i in range(n):
    arr[i] = int(arr[i])
x = 0
y = sum(arr)
for i in range(n):
    if x <= y:
        x += arr[i]
        y -= arr[i]
        ans.append(x - y)
ans = map(abs,ans)
print(min(ans))

### FIXED CODE ###

n = int(input())
arr = list(map(int,input().split()))
sum_arr = sum(arr)
ans=[]
x = 0
for i in range(n-1):
    x += arr[i]
    y = sum_arr - x
    ans.append(abs(x - y))
print(min(ans))
S = str(input())
T = str(input())
a = len(S)
b = len(T)
if (a < b):
    print("UNRESTORABLE")
    exit()
m = a-b
B = "UNRESTORABLE"
for i in range(m+1):
    for j in range(b):
        if S[i+j] == T[j]:
            S =S.replace(S[i:i+b+1], T)
            S = S.replace('?', 'a')
            B = S
            break
            
            
print(B)

### FIXED CODE ###

S = input()
T = input()
if len(S) < len(T):
    print('UNRESTORABLE')
    exit()

candidates = []
for i in range(len(S) - len(T) + 1):
    for c1,c2 in zip(S[i:i+len(T)], T):
        if c1 != '?' and c1 != c2:
            break
    else:
        cand = S[:i] + T + S[i+len(T):]
        candidates.append(cand.replace('?','a'))

if candidates:
    print(min(candidates))
else:
    print('UNRESTORABLE')
#!/usr/bin/env python3
import sys
MOD = 1000000007  # type: int

def permutations_count(n, k):
    if k == 0:
        return 1
    return n * permutations_count(n-1, k-1) % MOD

def solve(N: int, K: int, a: "List[int]", b: "List[int]"):
    matrix = [[] for _ in range(N+1)]
    for i in range(N-1):
        matrix[a[i]].append(b[i])
        matrix[b[i]].append(a[i])
    
    visited = [0]*(N+1)

    from collections import deque
    queue = deque()
    visited[1]=1
    answer = K

    if K-1 < len(matrix[1]):
        print(0)
        return

    answer *= permutations_count(K-1,len(matrix[1]))
    for node in matrix[1]:
        queue.append(node)

    while queue:
        q = queue.popleft()

        if visited[q] == 0:
            if K-2 < len(matrix[q])-1:
                print(0)
                return
            answer *= permutations_count(K-2,len(matrix[q])-1) #親ノード引いてる
        else:
            continue

        visited[q] = 1

        for child_node in matrix[q]:
            if child_node != q:
                queue.append(child_node)

    print(answer%MOD)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    a = [int()] * (N - 1)  # type: "List[int]"
    b = [int()] * (N - 1)  # type: "List[int]"
    for i in range(N - 1):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    solve(N, K, a, b)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
MOD = 1000000007  

def solve(N: int, K: int, a: "List[int]", b: "List[int]"):
    matrix = [[] for _ in range(N+1)]
    for i in range(N-1):
        matrix[a[i]].append(b[i])
        matrix[b[i]].append(a[i])
    
    visited = [0]*(N+1)

    from collections import deque
    queue = deque()
    visited[1]=1
    answer = K
    num = K-1
    for node in matrix[1]:
        answer *= num
        answer %= MOD

        num -= 1
        queue.append(node)

    while queue:
        q = queue.popleft()
        if visited[q] != 0:
            continue
        visited[q] = 1

        num = K-2
        for child_node in matrix[q]:
            if visited[child_node] == 0:
                answer *= num
                answer %= MOD
                num -= 1
                queue.append(child_node)
        answer %= MOD

    print(answer%MOD)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    a = [int()] * (N - 1)  # type: "List[int]"
    b = [int()] * (N - 1)  # type: "List[int]"
    for i in range(N - 1):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    solve(N, K, a, b)

if __name__ == '__main__':
    main()