Problem:
 Score : 500 points    Problem Statement You are given a tree with N vertices and N-1 edges. The vertices are numbered 1 to N , and the i -th edge connects Vertex a_i and b_i .  You have coloring materials of K colors.
For each vertex in the tree, you will choose one of the K colors to paint it, so that the following condition is satisfied:   If the distance between two different vertices x and y is less than or equal to two, x and y have different colors.   How many ways are there to paint the tree? Find the count modulo 1\ 000\ 000\ 007 .   What is tree? A tree is a kind of graph. For detail, please see: Wikipedia "Tree (graph theory)"

Solution (Python):
import sys

def getpar(Edge, p):
    N = len(Edge)
    par = [0]*N
    par[0] = -1
    par[p]  -1
    stack = [p]
    visited = set([p])
    while stack:
        vn = stack.pop()
        for vf in Edge[vn]:
            if vf in visited:
                continue
            visited.add(vf)
            par[vf] = vn
            stack.append(vf)
    return par

def topological_sort_tree(E, r):
    Q = [r]
    L = []
    visited = set([r])
    while Q:
        vn = Q.pop()
        L.append(vn)
        for vf in E[vn]:
            if vf not in visited:
                visited.add(vf)
                Q.append(vf)
    return L

def getcld(p):
    res = [[] for _ in range(len(p))]
    for i, v in enumerate(p[1:], 1):
        res[v].append(i)
    return res

mod = 10**9+7
frac = [1]*114514
for i in range(2,114514):
    frac[i] = i * frac[i-1]%mod
fraci = [None]*114514
fraci[-1] = pow(frac[-1], mod -2, mod)
for i in range(-2, -114514-1, -1):
    fraci[i] = fraci[i+1] * (114514 + i + 1) % mod
def perm(a, b):
    if not a >= b >= 0:
        return 0
    return frac[a]*fraci[a-b]%mod

N, K = map(int, input().split())
Dim = [0]*N
Edge = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, sys.stdin.readline().split())
    a -= 1
    b -= 1
    Edge[a].append(b)
    Edge[b].append(a)
    Dim[a] += 1
    Dim[b] += 1

P = getpar(Edge, 0)
L = topological_sort_tree(Edge, 0)
C = getcld(P)

dp = [0]*N
dp[0] = K
decided = [0]*N
for i in range(1, N):
    l = L[i]
    p = P[l]
    lcp = len(C[p])
    dp[l] = (K - lcp + decided[p] - (p != 0)) 
    decided[p] += 1
ans = 1
for d in dp:
    ans = ans * d % mod
print(ans)

Solution (Python):
import sys
from collections import deque
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return list(map(int, sys.stdin.readline().split()))

def main():
    n, k = LI()
    g = [[] for i in range(n+1)]
    for i in range(n-1):
        a, b = LI()
        g[a].append(b)
        g[b].append(a)

    s = 1
    Q = deque([s])
    ans = k
    Qappend = Q.append
    searched = [0] * (n+1)
    searched[s] = 1
    while len(Q) != 0:
        temp = 1
        v = Q.popleft()
        if v == s:
            cand = k - 1
        else:
            cand = k - 2
        for i in g[v]:
            if searched[i] == 1:
                continue
            searched[i] = 1
            temp = temp * cand % MOD
            cand -= 1
            Qappend(i)
        ans = ans * temp % MOD
    print(ans % MOD)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
from collections import deque
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return list(map(int, sys.stdin.readline().split()))

def main():
    n, k = LI()
    g = [[] for i in range(n+1)]
    for i in range(n-1):
        a, b = LI()
        g[a].append(b)
        g[b].append(a)

    s = 1
    Q = deque([s])
    ans = k
    Qappend = Q.append
    searched = [0] * (n+1)
    searched[s] = 1
    while len(Q) != 0:
        temp = 1
        v = Q.popleft()
        if v == s:
            cand = k - 1
        else:
            cand = k - 2
        for i in g[v]:
            if searched[i] == 1:
                continue
            searched[i] = 1
            temp = temp * cand % MOD
            cand -= 1
            Qappend(i)
        ans = ans * temp % MOD
    print(ans % MOD)


if __name__ == "__main__":
    main()

Solution (Python):


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()

Solution (Python):

def solve():
    N, K = map(int, input().split())
    N_1 = [{1},{0}]+[set() for _ in range(N-1)]
    for _ in range(N-1):
        a, b = map(int, input().split())
        N_1[a].add(b)
        N_1[b].add(a)
    checked, q = set(), {0}
    res = 1
    while q:
        n = q.pop()
        checked.add(n)
        q.update(set.difference(N_1[n], checked))
        K_ = K-min(2,n)
        for i in range(len(N_1[n])-(n>0)):
            if K_ == i:
                return str(0)
            res = (res*(K_-i))%(10**9+7)
    return str(res)
if __name__ == '__main__':
    print(solve())

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return list(map(int, sys.stdin.readline().split()))

def main():
    n, k = LI()
    g = [[] for i in range(n+1)]
    for i in range(n-1):
        a, b = LI()
        g[a].append(b)
        g[b].append(a)

    s = 1
    Q = [s]
    ans = k
    Qappend = Q.append
    searched = [0] * (n+1)
    searched[s] = 1
    while len(Q) != 0:
        temp = 1
        v = Q.pop()
        if v == s:
            cand = k - 1
        else:
            cand = k - 2
        for i in g[v]:
            if searched[i] == 1:
                continue
            searched[i] = 1
            temp = temp * cand % MOD
            cand -= 1
            Qappend(i)
        ans = ans * temp % MOD
    print(ans % MOD)


if __name__ == "__main__":
    main()

Solution (Python):
from collections import defaultdict, deque
import sys
sys.setrecursionlimit(100000)

MIN = -10 ** 9
MAX = 10 ** 9 + 7


def main():
    N, K = [int(a) for a in input().split()]
    if N == 1:
        print(K)
        return
    if K == 1:
        print(0)
        return

    ab = [
        [int(a) for a in input().split()]
        for _ in range(N - 1)
    ]

    edges = defaultdict(lambda: [])
    for ai, bi in ab:
        r = edges[ai]
        r.append(bi)
        edges[ai] = r
        r = edges[bi]
        r.append(ai)
        edges[bi] = r

    childrentable = [None] * (N + 1)

    q = deque()
    q.append((None, 1))

    while len(q) != 0:
        parent_i, current_i = q.pop()

        children = []
        for nei in edges[current_i]:
            if nei == parent_i:
                continue
            q.append((current_i, nei))
            children.append(nei)
        childrentable[current_i] = children

    if len(childrentable[1]) > K - 1:
        print(0)
        return

    def c(a, b):
        k = 1
        for i in range(b):
            if a - i <= 0:
                raise ValueError()
            k = (k * (a - i)) % MAX
        return k

    def f(index):
        target = childrentable[index]
        childcount = len(target)

        a = c(K - 2, childcount)
        for child in target:
            r = f(child) % MAX
            a = (a * r) % MAX
        return a

    try:
        result = K * c((K - 1), len(childrentable[1]))
        for child in childrentable[1]:
            r = f(child) % MAX
            result = (result * r) % MAX
    except:
        print(0)
        return
    print(result)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return list(map(int, sys.stdin.readline().split()))

def main():
    n, k = LI()
    g = [[] for i in range(n+1)]
    for i in range(n-1):
        a, b = LI()
        g[a].append(b)
        g[b].append(a)

    s = 1
    Q = [s]
    ans = k
    Qappend = Q.append
    searched = [0] * (n+1)
    searched[s] = 1
    while len(Q) != 0:
        temp = 1
        v = Q.pop()
        if v == s:
            cand = k - 1
        else:
            cand = k - 2
        for i in g[v]:
            if searched[i] == 1:
                continue
            searched[i] = 1
            temp = temp * cand % MOD
            cand -= 1
            Qappend(i)
        ans = ans * temp % MOD
    print(ans % MOD)


if __name__ == "__main__":
    main()

Solution (Python):
from collections import defaultdict

class Combinatorics:
    def __init__(self, N, mod):
        '''
        Preprocess for calculating binomial coefficients nCr (0 <= r <= n, 0 <= n <= N)
        over the finite field Z/(mod)Z.
        Input:
            N (int): maximum n
            mod (int): a prime number. The order of the field Z/(mod)Z over which nCr is calculated.
        '''
        self.mod = mod
        self.fact = {i: None for i in range(N+1)}         
        self.inverse = {i: None for i in range(1, N+1)}   
        self.fact_inverse = {i: None for i in range(N+1)} 
        
        
        self.fact[0] = self.fact[1] = 1
        self.fact_inverse[0] = self.fact_inverse[1] = 1
        self.inverse[1] = 1
        for i in range(2, N+1):
            self.fact[i] = i * self.fact[i-1] % self.mod
            q, r = divmod(self.mod, i)
            self.inverse[i] = (- (q % self.mod) * self.inverse[r]) % self.mod
            self.fact_inverse[i] = self.inverse[i] * self.fact_inverse[i-1] % self.mod
    
    def perm(self, n, r):
        '''
        Calculate nPr = n! / (n-r)! % mod
        '''
        if n < r or n < 0 or r < 0:
            return 0
        else:
            return (self.fact[n] * self.fact_inverse[n-r]) % self.mod
    
    def binom(self, n, r):
        '''
        Calculate nCr = n! /(r! (n-r)!) % mod
        '''
        if n < r or n < 0 or r < 0:
            return 0
        else:
            return self.fact[n] * (self.fact_inverse[r] * self.fact_inverse[n-r] % self.mod) % self.mod
        
    def hom(self, n, r):
        '''
        Calculate nHr = {n+r-1}Cr % mod.
        Assign r objects to one of n classes.
        Arrangement of r circles and n-1 partitions:
            o o o | o o | | | o | | | o o | | o
        '''
        if n == 0 and r > 0:
            return 0
        if n >= 0 and r == 0:
            return 1
        return self.binom(n + r - 1, r)

N, K = map(int, input().split())
E = defaultdict(list)
MOD = 10**9 + 7
for _ in range(N-1):
    a, b = map(int, input().split())
    E[a-1].append(b-1)
    E[b-1].append(a-1)
com = Combinatorics(K, MOD)
ans = K
parent = [None]*N
seen = [False]*N
parent[0] = -1
seen[0] = True
stack = [0]
while stack:
    v = stack.pop()
    n_children = len(E[v]) - (0 if v == 0 else 1)
    if n_children == 0: continue
    ans = (ans * com.perm(K - (1 if v == 0 else 2), n_children)) % MOD
    for u in E[v]:
        if seen[u]: continue
        parent[u] = v
        seen[u] = True
        stack.append(u)
print(ans)

Solution (Python):
import sys,collections as cl,bisect as bs,math
sys.setrecursionlimit(100000)
Max = sys.maxsize
from math import factorial

def l(): 
	return list(map(int,input().split()))
def m(): 
	return map(int,input().split())
def onem(): 
	return int(input())
def s(x): 
	a = []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa == x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x): 
	return " ".join(map(str,x))
def max2(x): 
	return max(map(max,x))
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    return g1[n] * g2[n-r] % mod

mod = 10**9+7 
N = 10**5
g1 = [1, 1] 
g2 = [1, 1] 
inverse = [0, 1] 

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )


n,k = m()

s = [[] for i in range(n)]

for i in range(n-1):
	a,z = m()
	s[a-1].append(z-1)
	s[z-1].append(a-1)

co = k * cmb(k-1,len(s[0]),mod)
co %= mod

def dfs(tree,now,be):
	global co,d
	if len(tree[now]) != 1:
		ma = k - 2
		mm = len(tree[now]) - 1
		co *= cmb(ma,mm,mod)
		co %= mod
		for i in range(mm+1):
			if s[now][i] != be:
				dfs(tree,s[now][i],now)


for i in range(len(s[0])):
	dfs(s,s[0][i],0)


print(co)

Solution (Python):
from collections import deque
import sys
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, d=DVSR): return pow(x, d - 2, d)
def DIV(x, y, d=DVSR): return (x * INV(y, d)) % d
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())


N,K=LI()
mp = {}

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

for i in range(N-1):
    a,b = LI()
    if not a in mp: mp[a] = []
    if not b in mp: mp[b] = []
    mp[a].append(b)
    mp[b].append(a)

QU = deque([])
visited = set([1])

fact=[1]*(max(N,K)+1)
for i in range(1, max(N,K)+1):
    fact[i] = fact[i-1]*i%DVSR

def ncr(n,r):
    return fact[n]*INV(fact[r])*INV(fact[n-r])%DVSR

pat = ncr(K, len(mp[1])+1)*fact[len(mp[1])+1]%DVSR
for i in mp[1]:
    visited.add(i)
    QU.append(i)


while QU:
    vx = QU.popleft()
    
    nxcnt = len(mp[vx])
    if (nxcnt+1) > K:
        print(0)
        exit()
    notvisited = 0
    for nx in mp[vx]:
        if not nx in visited:
            QU.append(nx)
            visited.add(nx)
    pat = pat*fact[nxcnt-1]*ncr(K-2, nxcnt-1)%DVSR

print(pat)

Solution (Python):
import sys
sys.setrecursionlimit(100000)
n,k=map(int,input().split())
ans=k
t=[set()for i in range(n)]
dp=[k]+[0]*(n-1)
for i in range(n-1):
  a,b=map(int,input().split())
  t[a-1].add(b)
  t[b-1].add(a)
no=1
w=k
def a(noo):
  global ans
  w=k
  for i in t[noo-1]:
    t[i-1].discard(noo)
    if w==0:print(0);exit()
    dp[i-1]=w-2;ans=(ans*(w-2))%(10**9+7)
    w-=1
    a(i)
for i in t[no-1]:
  t[i-1].discard(no)
  w-=1
  dp[i-1]=w;ans=(ans*w)%(10**9+7)
  a(i)
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
INF=10**9+7
def LI(): return list(map(int, sys.stdin.readline().split()))

def main():
    n, k = LI()
    graph=[[] for i in range(n)]
    for i in range(n-1):
        a,b=LI()
        graph[a-1].append(b-1)
        graph[b-1].append(a-1)
    ans=1
    check=[False]*n
    stack=[0]
    ans=1
    while len(stack)>0:
        x=stack.pop()
        check[x]=True
        count=0
        for i in graph[x]:
            if not check[i]:
                count+=1
                stack.append(i)
        if x==0:
            temp=1
            for i in range(count):
                temp=temp*(k-1-i)%INF
            ans=ans*temp%INF
        else:
            temp=1
            for i in range(count):
                temp=temp*(k-2-i)%INF
            ans=ans*temp%INF
    print((ans*k)%INF)


if __name__ == "__main__":
    main()

Solution (Python):


import sys

n,k = [ int(x) for x in sys.stdin.readline().split() ]
d1 = [ [] for _ in range(n) ]
for _ in range(n-1):
    ai,bi = [ int(x)-1 for x in sys.stdin.readline().split() ]
    d1[ai].append( bi )
    d1[bi].append( ai )

flag = [ True ] * n
flag[0] = False
total = k
now = k
nxt = [ d1[0] ]
while nxt:
    tmp= []
    for points in nxt:
        if now!=k: now= k-1
        for v in points:
            if not flag[v]: continue
            flag[v]= False
            tmp.append(v)
            now -= 1
            total= ( total * now ) % 1000000007
    
    nxt= []
    for v in tmp:
        a= [ vv for vv in d1[v] if flag[vv] ]
        if a: nxt.append( a )

print( total )

Solution (Python):
def BC133_E():
    n, k = map(int, input().split())
    d = [set() for _ in range(n)]
    for _ in range(n - 1):
        a, b = map(int, input().split())
        d[a - 1].add(b - 1)
        d[b - 1].add(a - 1)
    stack = [(0, 0)]
    visited = set()
    res = []
    while stack:
        i, l = stack.pop(0)
        visited.add(i)
        c = len(d[i] - visited)
        if c != 0:
            if l == len(res):
                res.append([c])
            else:
                res[l].append(c)
        for j in d[i]:
            if j not in visited: stack.append((j, l + 1))
    ans = k
    MOD = 10**9 + 7
    for i in range(len(res)):
        if i == 0:
            c = k - 1
            for m in range(res[0][0] - 1):
                c = ((k - m - 2) * c) % MOD
            ans = (ans * c) % MOD
        else:
            for j in res[i]:
                c = k - 2
                for m in range(j - 1):
                    c = ((k - m - 3) * c) % MOD
                ans = (ans * c) % MOD
    print(ans)


BC133_E()

Solution (Python):
import sys,heapq,resource
from collections import deque,defaultdict
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True 
R = 10**9 + 7
def ddprint(x):
  if DBG:
    print(x)

def perm(k,d):
    x = k
    for i in range(1,d):
        x = (x * (k-i)) % R
    return x

def dfs(prev, cur):
    d = len(dst[cur])-1
    if d==0:
        return 1
    x = perm(k-2,d)
    for nd in dst[cur]:
        if nd==prev:
            continue
        x = (x * dfs(cur,nd)) % R
    return x

def setrlim():
    sys.setrecursionlimit(250000)
    soft,hard = resource.getrlimit(resource.RLIMIT_STACK)
    resource.setrlimit(resource.RLIMIT_STACK,(128*1024*1024,hard))

setrlim()
n,k = inm()
dst = [ [] for i in range(n) ]
for i in range(n-1):
    a,b = inm()
    a -= 1
    b -= 1
    dst[a].append(b)
    dst[b].append(a)

for i in range(n):
    if len(dst[i]) >= k:
        print(0)
        exit()

d = len(dst[0])
x = perm(k,d+1)
for nd in dst[0]:
    x = (x * dfs(0,nd)) % R
print(x)

Solution (Python):
import sys
sys.setrecursionlimit(10**8)

N,K = map(int,input().split(' '))
l = [list(map(int,input().split())) for _ in range(N-1)]
p = 10**9+7
MAP = [[] for i in range(N + 1)]

for a, b in l:
    MAP[a].append(b)
    MAP[b].append(a)
visited = [False]*(N+1)

def dfs(i,f,s):
    if visited[i]:
        return 1
    b = f + s
    res = K - b
    s = f
    f = 1
    visited[i] = True
    for v in MAP[i]:
        if visited[v]:
            continue
        res *= dfs(v,f,s)
        res %= p
        s += 1
    return res if res > 0 else 0
print(dfs(1,0,0))

Solution (Python):
import sys
from collections import defaultdict
sys.setrecursionlimit(10**6)

def main():
    input = sys.stdin.readline
    MOD = 10**9 + 7
    N, K = map(int, input().split())
    G = defaultdict(list)
    for _ in range(N-1):
        a, b = map(int, input().split())
        a, b = a-1, b-1

        G[a].append(b)
        G[b].append(a)

    visited = [False] * N
    def dfs(n, ans):
        child = 1
        if n == 0:
            child = 0

        visited[n] = True
        for c in G[n]:
            if visited[c]:
                continue
            ans = (ans * (K - 1 - child)) % MOD
            ans = dfs(c, ans)
            child += 1

        return ans

    return dfs(0, K)


if __name__ == '__main__':
    print(main())

Solution (Python):
import sys,heapq,resource
from collections import deque,defaultdict
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True 
R = 10**9 + 7
def ddprint(x):
  if DBG:
    print(x)

def perm(k,d):
    x = k
    for i in range(1,d):
        x = (x * (k-i)) % R
    return x

def dfs(prev, cur):
    d = len(dst[cur])-1
    if d==0:
        return 1
    x = perm(k-2,d)
    for nd in dst[cur]:
        if nd==prev:
            continue
        x = (x * dfs(cur,nd)) % R
    return x

sys.setrecursionlimit(250000)
soft,hard = resource.getrlimit(resource.RLIMIT_STACK)
resource.setrlimit(resource.RLIMIT_STACK,(128*1024*1024,hard))
n,k = inm()
dst = [ [] for i in range(n) ]
for i in range(n-1):
    a,b = inm()
    a -= 1
    b -= 1
    dst[a].append(b)
    dst[b].append(a)

for i in range(n):
    if len(dst[i]) >= k:
        print(0)
        exit()

d = len(dst[0])
x = perm(k,d+1)
for nd in dst[0]:
    x = (x * dfs(0,nd)) % R
print(x)

Solution (Python):
import sys
input = sys.stdin.readline

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

ans = K
visit = [False]*(N+1)
visit[1] = True
queue = tree[1][:]
for i in range(len(queue)):
    ans *= K-1-i
    ans %= 1000000007
    visit[queue[i]] = True


while len(queue) > 0:
    nextqueue = []
    for now in queue:
        nexttemp = []
        for next in tree[now]:
            if not visit[next]:
                nexttemp.append(next)
                visit[next] = True
        nextqueue.extend(nexttemp)
        for i in range(len(nexttemp)):
            ans *= K-2-i
            ans %= 1000000007
    queue = nextqueue[:]

print(ans)

Solution (Python):
import sys
from collections import deque


MOD = 10 ** 9 + 7
fin = sys.stdin.readline
N, K = [int(elem) for elem in fin().split()]
adj = [[] for _ in range(N)]
for _ in range(N - 1):
    a, b = [int(elem) for elem in fin().split()]
    a -= 1
    b -= 1
    adj[a].append(b)
    adj[b].append(a)

num_patterns = K
que = deque()
que.append((0, -1))
while que:
    node, parent = que.popleft()
    num_available_color = K - 1 if parent == -1 else K - 2
    for i in range(len(adj[node]) - (0 if parent == -1 else 1)):
        if (i >= num_available_color):
            print(0)
            exit(0)
        num_patterns *= num_available_color - i
        num_patterns %= MOD
    for neighbor in adj[node]:
        if neighbor == parent:
            continue
        que.append((neighbor, node))
print(num_patterns)

Solution (Python):
def BC133_E():
    n, k = map(int, input().split())
    d = [[] for _ in range(n)]
    for _ in range(n - 1):
        a, b = map(int, input().split())
        d[a - 1].append(b - 1)
        d[b - 1].append(a - 1)
    stack = [(0, 0)]
    visited = set()
    res = []
    while stack:
        i, l = stack.pop(0)
        visited.add(i)
        c = len(set(d[i]) - visited)
        if c != 0:
            if l == len(res):
                res.append([c])
            else:
                res[l].append(c)
        for j in d[i]:
            if j not in visited: stack.append((j, l + 1))
    ans = k
    MOD = 10**9 + 7
    for i in range(len(res)):
        if i == 0:
            c = k - 1
            for m in range(res[0][0] - 1):
                c = ((k - m - 2) * c) % MOD
            ans = (ans * c) % MOD
        else:
            for j in res[i]:
                c = k - 2
                for m in range(j - 1):
                    c = ((k - m - 3) * c) % MOD
                ans = (ans * c) % MOD
    print(ans)


BC133_E()

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')


def A():
    n, a, b = LI()
    print(min(n * a, b))
    return


def B():
    n, d = LI()
    x = LIR(n)
    a = list(itertools.combinations(range(n), 2))
    ans = 0
    for a1,a2 in a:
        b = 0
        for bi in range(d):
            b += (x[a1][bi] - x[a2][bi])** 2
        if float.is_integer(math.sqrt(b)):
            ans += 1
    print(ans)
    return


def C():
    l, r = LI()
    ans = 2018
    if l // 2019 == r // 2019:
        for i in range(l, r + 1):
            for k in range(i+1, r + 1):
                ans = min(ans, (i * k) % 2019)
        print(ans)
    else:
        print(0)
    return


def D():
    n = II()
    a = LI()
    a = a + [a[0]]
    ans = [0] * n
    x = 0
    for i in range(1, n, 2):
        x = x + a[i + 1] - a[i]
    ans[1] = a[0] - x
    ans[0] = ans[1] + 2 * x
    for i in range(2, n):
        ans[i] = (a[i - 1] - ans[i - 1] // 2) * 2
    print(" ".join(map(str, ans)))

    return


def E():
    n, k = LI()
    ab = LIR_(n - 1)
    edg = [[] for i in range(n)]
    for a,b in ab:
        edg[a].append(b)
        edg[b].append(a)
    check = defaultdict(int)
    chb = defaultdict(lambda: True)
    ans = k
    q = deque()
    for i in edg[0]:
        check[i] = 1
        q.append(i)
    check[0] = 1
    chb[0] = False
    while q:
        i = q.pop()
        chb[i] = False
        b = 0
        x = 0
        for e in edg[i]:
            b += check[e]
            check[e] += 1
            if chb[e]:
                q.appendleft(e)
            else:
                x += 1
        check[i] = x + 1
        ans *= (k - b)
        ans %= mod
    print(ans)
    return


def F():
    return


def G():
    return


def H():
    return


if __name__ == '__main__':
    E()

Solution (Python):
MOD = 1000000007

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

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

uv = {}
for i in range(N-1):
    a, b = map(int, input().split())
    if a in uv:
        uv[a].append(b)
    else:
        uv[a] = [b]

    if b in uv:
        uv[b].append(a)
    else:
        uv[b] = [a]

f = None
for u in uv:
    if len(uv[u]) == 1:
        f = u
        break

ans = 1
b = [False] * (N+1)
ulist = [[f, 0]]
while ulist:
    u, pNum = ulist[-1]
    ulist.pop()
    b[u] = True

    uPtn = K - pNum
    ans = ans*uPtn % MOD

    cnt = 1
    if pNum == 0:
        cnt = 0
    for v in uv[u]:
        if b[v]:
            continue
        ulist.append([v, 1 + cnt])
        cnt += 1

print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**9)

def dfs(v,mod):
  cnt=0
  ret=1
  for i in g[v]:
    if checked[i]==0:
      checked[i]=1
      cnt+=1
      ret=(ret*dfs(i,mod))%mod
  for i in range(cnt):
    ret=(ret*(k-2-i))%mod
  return ret
  
n,k=map(int,input().split())
g=[[] for _ in range(n+1)]
for _ in range(n-1):
  a,b=map(int,input().split())
  g[a].append(b)
  g[b].append(a)
mod=10**9+7
checked=[0]*(n+1)
checked[1]=1
ans=k
for i in range(len(g[1])):
  ans=(ans*(k-1-i))%mod
for i in g[1]:
  checked[i]=1
  ans=(ans*dfs(i,mod))%mod
print(ans)

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')


def A():
    n, a, b = LI()
    print(min(n * a, b))
    return


def B():
    n, d = LI()
    x = LIR(n)
    a = list(itertools.combinations(range(n), 2))
    ans = 0
    for a1,a2 in a:
        b = 0
        for bi in range(d):
            b += (x[a1][bi] - x[a2][bi])** 2
        if float.is_integer(math.sqrt(b)):
            ans += 1
    print(ans)
    return


def C():
    l, r = LI()
    ans = 2018
    if l // 2019 == r // 2019:
        for i in range(l, r + 1):
            for k in range(i+1, r + 1):
                ans = min(ans, (i * k) % 2019)
        print(ans)
    else:
        print(0)
    return


def D():
    n = II()
    a = LI()
    a = a + [a[0]]
    ans = [0] * n
    x = 0
    for i in range(1, n, 2):
        x = x + a[i + 1] - a[i]
    ans[1] = a[0] - x
    ans[0] = ans[1] + 2 * x
    for i in range(2, n):
        ans[i] = (a[i - 1] - ans[i - 1] // 2) * 2
    print(" ".join(map(str, ans)))

    return


def E():
    n, k = LI()
    ab = LIR_(n - 1)
    edg = [[] for i in range(n)]
    for a,b in ab:
        edg[a].append(b)
        edg[b].append(a)
    check = defaultdict(int)
    chb = defaultdict(lambda: True)
    ans = k
    q = deque()
    for i in edg[0]:
        check[i] = 1
        q.append(i)
        chb[i] = False
    check[0] = 1
    chb[0] = False
    while q:
        i = q.pop()
        chb[i] = False
        b = 0
        x = 0
        for e in edg[i]:
            b += check[e]
            check[e] += 1
            if chb[e]:
                q.appendleft(e)
            else:
                x += 1
        check[i] = x + 1
        ans *= (k - b)
        ans %= mod
    print(ans)
    return


def F():
    return


def G():
    return


def H():
    return


if __name__ == '__main__':
    E()

Solution (Python):
mod = 10 ** 9 + 7
n,k = map(int,input().split())
lis = [[] for i in range(n)]
for i in range(n-1):
    a,b = map(int,input().split())
    lis[a-1] += [b-1]
    lis[b-1] += [a-1]
li = [0] * n
l = [0]
li[0] = 1
ans = k
while l:
    ll = l.pop()
    for lll in lis[ll]:
        if li[lll] > 0:
            continue
        else:
            ans = (ans * max(k-li[ll],0))%mod
            li[ll] += 1
            li[lll] = 2
            l.append(lll)
print(ans%mod)