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):
N,K=map(int,input().split())
A=[list(map(int,input().split())) for i in range(N-1)]
m=10**9+7
c=[[] for i in range(N)]
for i,j in A:
    c[i-1].append(j-1)
    c[j-1].append(i-1)
import sys
sys.setrecursionlimit(10**6)
def bfs(p):
    r=K
    d=1
    n=[1]*N
    while len(p)>0:
        q=[]
        for e in p:
            n[e]=0
            x=max(K-min(2,d),0)
            for f in c[e]:
                if n[f]:
                    q.append(f)
                    r=(r*x)%m
                    x-=1
        p=q
        d+=1
    return r
print(bfs([A[0][0]-1]) if N>1 else K)

Solution (Python):
n,k = map(int,input().split())
from collections import deque
l = [[] for _ in range(n)]
for i in range(n-1):
    ta,tb = map(int,input().split())
    l[ta-1].append(tb-1)
    l[tb-1].append(ta-1)
c,q = k,deque([0])

while q:
    v,i = q.pop(),1
    for w in l[v]:
        c = c*(k-i-(v>0))%(10**9+7)
        l[w].remove(v)
        q.append(w)
        i+=1
print(c)

Solution (Python):
from collections import deque
p = 10**9+7
N,K = map(int,input().split())
G = {i:[0,[]] for i in range(1,N+1)}
for _ in range(N-1):
    a,b = map(int,input().split())
    G[a][1].append(b)
    G[b][1].append(a)
que = deque([1])
hist = [0 for _ in range(N+1)]
hist[1] = 1
A = [0 for _ in range(N+1)]
while que:
    x = que.popleft()
    for y in G[x][1]:
        if hist[y]==0:
            A[y] = 1+G[x][0]
            G[x][0] += 1
            G[y][0] += 1
            que.append(y)
            hist[y] = 1
cnt = 1
for i in range(1,N+1):
    cnt = (cnt*(K-A[i]))%p
print(cnt)

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def inv(x):
    return pow(x, mod - 2, mod)

cms = 10**5 + 5
cm = [0] * cms

def comb_init():
    cm[0] = 1
    for i in range(1, cms):
        cm[i] = cm[i-1] * i % mod

def comb(a, b):
    return (cm[a] * inv(cm[a-b]) % mod) * inv(cm[b]) % mod

def main():
    n,k = LI()
    ab = [LI_() for _ in range(n-1)]
    e = collections.defaultdict(list)
    for a,b in ab:
        e[a].append(b)
        e[b].append(a)

    for v in e.values():
        if len(v) >= k:
            return 0

    comb_init()
    def f(i, p):
        el = len(e[i])
        if p == -1:
            r = comb(k-1, el) * cm[el] % mod
        else:
            r = comb(k-2, el-1) * cm[el-1] % mod
        for c in e[i]:
            if c == p:
                continue
            r *= f(c, i)
            r %= mod
        return r

    r = f(0,-1) * k


    return r % mod


print(main())

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

MOD = 1000000007

class Factorial():
    def __init__(self,n,mod):
        self.mod = mod
        self.factorial = [0 for _ in range(n+1)]
        self.inv = [0 for _ in range(n+1)]
        self.factorial[0] = 1
        self.inv[0] = 1
        for i in range(n):
            self.factorial[i+1] = self.factorial[i]*(i+1)%mod
            self.inv[i+1] = self.inv[i]*pow(i+1,mod-2,mod)%mod
    def comb(self,m,k):
        return self.factorial[m]*self.inv[k]*self.inv[m-k]%self.mod
    def fact(self,m):
        return self.factorial[m]
    def perm(self,m,k):
        return self.factorial[m]*self.inv[m-k]%self.mod
    def invfact(self,m):
        return self.inv[m]

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

tree = [[] for _ in range(N)]

for _ in range(N-1):
    a,b = map(int,input().split())
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)
    
visited = [0 for _ in range(N)]
visited[0] = 1
queue = deque([0])
ans = K

f = Factorial(K+1,MOD)

while queue:
    node = queue.popleft()
    count = 0
    for adj in tree[node]:
        if not visited[adj]:
            visited[adj] = 1
            queue.append(adj)
            count += 1
    if node==0:
        if K-1 < count:
            print(0)
            break
        ans *= f.perm(K-1,count)
    else:
        if K-2 < count:
            print(0)
            break
        ans *= f.perm(K-2,count)
    ans %= MOD
            
else:
    print(ans)

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

































n,k = inpl()
g = [[] for i in range(n)]
seen = [-1]*n
for i in range(n-1):
    a,b = inpl()
    g[a-1].append(b-1)
    g[b-1].append(a-1)
def p(n,i):
    count = 1
    for _ in range(i):
        count = count * n % mod
        n -= 1
    return count
def dfs(cur,par=-1):
    res = 1
    c = 0 if par == -1 else 1
    cnt = 0
    for v in g[cur]:
        if v == par:
            continue
        cnt += 1
        res *= dfs(v,cur)
        res %= mod
    return res*p(k-c-1,cnt)
print(dfs(0,-1)*k%mod)

Solution (Python):
from collections import deque
N, K = map(int, input().split())
tree = [[] for i in range(N)]

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

depth = [-1]*N
mod = 10**9+7


next_v = deque([0])
depth[0] = 0
ans = K
while next_v:
    s = next_v.popleft()
    color = max(K-depth[s]-1, K-2)

    for t in tree[s]:
        if depth[t] != -1:
            continue
        next_v.append(t)
        depth[t] = depth[s] + 1

        ans *= color
        ans %= mod
        color -= 1

print(ans)

Solution (Python):

n, k = map(int, input().split())
reach = [[] for _ in range(n)]
mod = 10**9 + 7
for i in range(n-1):
    a, b = map(lambda x: int(x)-1, input().split())
    reach[a].append(b)
    reach[b].append(a)

def kai(i, j, mod):
    tmp = 1
    for x in range(i, i-j, -1):
        tmp *= x
        tmp %= mod
    return tmp

def dfs(st, n, k, reach, mod):
    check = [0] * n
    stack = [st]
    ans = k
    check[st] = 1
    while len(stack) > 0:
        tmp = stack.pop(-1)
        tmp_list = reach[tmp]
        alredy = 1
        yet = 0
        for i in tmp_list:
            if check[i] != 1:
                stack.append(i)
                check[i] = 1
                yet += 1
            else:
                alredy += 1
        t = kai(k-alredy, yet, mod)
        ans *= t
        ans %= mod
    return ans

ans = dfs(0, n, k, reach, mod)
print(ans)

Solution (Python):

n, k = map(int, input().split())
reach = [[] for _ in range(n)]
mod = 10**9 + 7
for i in range(n-1):
    a, b = map(lambda x: int(x)-1, input().split())
    reach[a].append(b)
    reach[b].append(a)

def kai(i, j, mod):
    tmp = 1
    for x in range(i, i-j, -1):
        tmp *= x
        tmp %= mod
    return tmp

def dfs(st, n, k, reach, mod):
    check = [0] * n
    stack = [st]
    ans = k
    check[st] = 1
    while len(stack) > 0:
        tmp = stack.pop(-1)
        tmp_list = reach[tmp]
        alredy = 1
        yet = 0
        for i in tmp_list:
            if check[i] != 1:
                stack.append(i)
                check[i] = 1
                yet += 1
            else:
                alredy += 1
        t = kai(k-alredy, yet, mod)
        ans *= t
        ans %= mod
    return ans

ans = dfs(0, n, k, reach, mod)
print(ans)

Solution (Python):



import sys
input = sys.stdin.readline

mod=10**9+7


N,K=map(int,input().split())
ab=[list(map(int, input().split())) for _ in range(N - 1)]
adj=[[] for _ in range(N)]

for a,b in ab:
    adj[a-1].append(b-1)
    adj[b-1].append(a-1)
    
    

P=[1]
for i in range(N):
    P.append((P[-1]*(K-2-i))%mod)
    

q=[(0,-1,0)]

ans=1
while q!=[]:
    v,p,d=q.pop()
    
    l=len(adj[v])
    if d==0:
        ans*=(K-1)
    ans*=(P[l-1])
    ans%=mod
    for i in range(l):
        next_v=adj[v][i]
        
        if next_v!=p and len(adj[next_v])!=1:
            q.append((next_v,v,d+1))
if N==1:
    ans=1
print((ans*K)%mod)

Solution (Python):
N,K=map(int,input().split())
E=[[] for i in range(N)]
for i in range(N-1):
  a,b=map(int,input().split())
  E[a-1].append(b-1)
  E[b-1].append(a-1)

DIV=10**9+7
ans=1
stack=[]

stack.append([0,K,-1])
while stack:
  node=stack.pop()
  v=node[0]
  color=node[1]
  parent=node[2]
  ans=((ans%DIV)*color)%DIV
  nextcolor=K-2
  if parent==-1:
    nextcolor=K-1
  children=E[v]
  for child in children:
    if child==parent:
      continue
    if nextcolor==0:
      ans=0
      break
    stack.append([child,nextcolor,v])
    nextcolor-=1
else:
  print(ans)

Solution (Python):
from collections import deque


def perm(n, k, a=1, mod=10**9+7):
  if n < k or k < 0:
    a = 0
  else:
    for i in range(n, n-k, -1):
      a = a*i % mod
  
  return a


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


ans = K
d = deque([[0, -1]])
while d:
  node, parent = d.pop()
  children = tree[node]
  if parent == -1:
    ans = ans*perm(K-1, len(children)) % MOD
  else:
    ans = ans*perm(K-2, len(children)-1) % MOD
  
  for child in children:
    if child == parent:
      continue
    
    d.append([child, node])

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
mod = 10**9+7
rng = 100001
fctr = [1]
finv = [1]
for i in range(1,rng):
    fctr.append(fctr[-1]*i%mod)
for i in range(1,rng):
    finv.append(pow(fctr[i],mod-2,mod))
n,k = map(int,input().split())
ab = [list(map(int, input().split(' '))) for i in range(n-1)]
graph = [[] for i in range(n+1)]
parent = [0 for i in range(n+1)]
cnum = [0 for i in range(n+1)]
root = 1
stack = [root]
ans = 1
for a,b in ab:
    graph[a].append(b)
    graph[b].append(a)
while stack:
    x = stack.pop()
    for y in graph[x]:
        if parent[x] == y:
            continue
        parent[y] = x
        cnum[x] += 1
        stack.append(y)
for x in range(1,n+1):
    if x == 1:
        y = cnum[1]
        if k-y-1<0:
            print(0)
            exit()
        ans = ans*fctr[k]*finv[k-y-1]%mod
        continue
    if cnum[x] == 0:
        continue
    y = cnum[x]
    if k-y-2<0:
        print(0)
        exit()
    ans = ans*fctr[k-2]*finv[k-2-y]%mod
print(ans)

Solution (Python):
def permu(n,r,p):
    result = 1
    for i in range(n,n-r,-1):
        result *= i
        result %= p
    return result

from collections import deque

n,k = map(int,input().split())
mod = 10**9 + 7
G = [[] for i in range(n)]
for i in range(n-1):
    x,y = map(int,input().split())
    x -= 1
    y -= 1
    G[x].append(y)
    G[y].append(x)

ans = k
s = True
que = deque([[-1,0]])
while que:
    pre,now = que.pop()

    if s:
        s = False
        ans *= permu(k-1,len(G[0]),mod)
        for nex in G[0]:
            que.append([0,nex])

    else:
        ans *= permu(k-2,len(G[now])-1,mod)
        for nex in G[now]:
            if nex == pre:continue
            que.append([now,nex])
    ans %= mod

print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
input = lambda: sys.stdin.readline().rstrip()
MOD = 10**9+7

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

for _ in range(n-1):
    a, b = map(int, input().split())
    a -= 1; b -= 1
    g[a].append(b)
    g[b].append(a)

cnt = [0] * n

def dfs(v, p):
    n_cnt = 1 if p == -1 else 2
    for nv in g[v]:
        if nv == p: continue
        cnt[nv] = n_cnt
        n_cnt += 1
        dfs(nv, v)

dfs(0, -1)
ans = 1

for x in cnt:
    ans *= max(0, (k - x))
    ans %= MOD

print(ans)

Solution (Python):
def prepare(m, mod=10 ** 9 + 7):
	fac = [1] * (m + 1)
	inv = [1] * (m + 1)
	for i in range(1, m + 1):
		fac[i] = fac[i - 1] * i % mod
	inv[-1] = pow(fac[-1], mod - 2, mod)
	for i in range(m - 1, -1, -1):
		inv[i] = inv[i + 1] * (i + 1) % mod
	return fac, inv

def main():
	n, k, *L = map(int, open(0).read().split())
	mod = 10 ** 9 + 7
	fac, inv = prepare(k)
	con = [[] for _ in range(n)]
	cnt = [0] * n
	vis = [False] * n
	for s, t in zip(*[iter(L)] * 2):
		con[s - 1] += [t - 1]
		con[t - 1] += [s - 1]
		cnt[s - 1] += 1
		cnt[t - 1] += 1
	if any(c + 1 > k for c in cnt):
		print(0)
		exit()
	q = [0]
	vis[0] = True
	ans = fac[k] * inv[k - cnt[0] - 1] % mod
	while q:
		cur = q.pop()
		for nxt in con[cur]:
			if vis[nxt]:
				continue
			ans *= fac[k - 2] * inv[k - cnt[nxt] - 1] % mod
			ans %= mod
			vis[nxt] = True
			q.append(nxt)
	print(ans)

if __name__ == "__main__":
	main()

Solution (Python):
N, K = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N - 1)]

MOD = 10 ** 9 + 7

graph = [[] for _ in range(N + 1)]
for A, B in AB:
  graph[A].append(B)
  graph[B].append(A)


parent = [-1] * (N + 1)

stack = [1]
parent[1] = 0
while stack:
  s = stack.pop()
  for g in graph[s]:
    if parent[s] != g:
      parent[g] = s
      stack.append(g)


cnt = [0] * (N + 1)
for i in range(2, len(parent)):
  cnt[parent[i]] += 1


P = [1]
for i in range(N + 2):
  P.append((P[-1] * (K - 2 - i)) % MOD)


answer = K
for i in range(1, len(cnt)):

  M = cnt[i]
  if M == 0:
    continue  
  

  if i == 1:
    if K - 1 >= M:
      for j in range(cnt[1]):
        answer *= (K - 1 - j)
        answer %= MOD
    else:
      answer = 0
  else:
    if K - 2 >= M:
      answer *= P[M]
      answer %= MOD
    else:
      answer = 0
print(answer)

Solution (Python):
def examA():
    N, A, B = LI()
    ans = min(A*N,B)
    print(ans)
    return

def examB():
    N, D = LI()
    X = [LI() for _ in range(N)]
    ans = 0
    for i,j in itertools.combinations(X,2):
        cur = 0
        for k in range(D):
            cur += (i[k]-j[k])**2
        cur **=0.5
        if cur==int(cur):
            ans +=1
    print(ans)
    return

def examC():
    L, R = LI()
    cur = []; ans = 10**9
    for i in range(L,min(2019+L,R)+1):
        if i%2019==0:
            ans = 0
            break
        else:
            cur.append(i%2019)
    if ans==0:
        print(ans)
        return
    N = len(cur)
    for i,j in itertools.combinations(cur,2):
        ans = min(ans,(i*j)%2019)
    print(ans)
    return

def examD():
    N = I()
    A = LI()
    dis = [0]*N
    for i in range(N):
        cur = A[i-N+1]-A[i-N]
        dis[i] = cur*2

    ans = [0]*N
    for i in range(2,2*N,2):
        ans[i-N] = ans[i-N-2] + dis[i-N-2]

    ad = (sum(A) - sum(ans))//N
    for i in range(N):
        ans[i] += ad
    print(" ".join(map(str,ans)))
    return

def bfs(n,e,fordfs,K):
    
    W = K
    que = deque()
    que.append(e)
    len = [10**9]*n
    len[e] = 0
    while que:
        now = que.popleft()
        nowlen = len[now]
        cur = K-min(2,nowlen+1)
        for ne in fordfs[now]:
            if len[ne] == 10**9:
                W *=cur; W %=mod
                cur -=1
                len[ne] = nowlen+1
                que.append(ne)
    return W
def examE():
    N, K = LI()
    V = [[]for _ in range(N)]
    for _ in range(N-1):
        a,b = LI()
        V[a-1].append(b-1)
        V[b-1].append(a-1)
    ans = bfs(N,0,V,K)
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,inf
mod = 10**9 + 7
inf = float('inf')

if __name__ == '__main__':
    examE()

Solution (Python):

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))  
    K = int(next(tokens))  
    a = [int()] * (N - 1)  
    b = [int()] * (N - 1)  
    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()

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

MOD = 1000000007
N, K = map(int, input().split())
edges = [[] for _ in range(N)]
for i in range(N-1):
    a, b = map(lambda x: int(x)-1, input().split())
    edges[a].append(b)
    edges[b].append(a)

colors = [K] + [0 for _ in range(N-1)]


def dfs(parent, edge, n):
    for child in edges[edge]:
        if child != parent:
            colors[child] = max(0, n)
            n -= 1
            dfs(edge, child, K-2)


def solve():
    dfs(0, 0, K-1)
    
    ans = K
    for color in colors[1:]:
        ans *= color
        ans %= MOD
    print(ans)


if __name__ == '__main__':
    solve()

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
n,k=map(int,input().split())
l=[[] for i in range(n+1)]
for i in range(n-1):
  a,b=map(int,input().split())
  l[a].append(b)
  l[b].append(a)
ans=[k]
mod=10**9+7
def dfs(s,p):
  if s==1:
    now=k-1
  else:
    now=k-2
  for i in l[s]:
    if i==p:
      pass
    else:
      ans[0]=(ans[0]*now)%mod
      now-=1
      dfs(i,s)
dfs(1,0)
print(ans[0])

Solution (Python):
import sys
def input():
    return sys.stdin.readline()[:-1]
import math
from itertools import permutations, combinations
from collections import defaultdict

sys.setrecursionlimit(10**7)
N, K = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(N-1)]
mod = 10**9+7

edges = [[] for _ in range(N)]
for abi in ab:
    a, b = abi[0], abi[1]
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)


res = K
def dfs(last, cur):
    global res

    if last == -1:
        for i, np in enumerate(edges[0]):
            res *= (K-i-1)
            res %= mod
            dfs(0, np)

    else:
        num_edges_cur = len(edges[cur]) - 1
        if num_edges_cur == 0:
            return

        for i in range(K-2, K-num_edges_cur-2, -1):
            res *= i
            res %= mod
        for np in edges[cur]:
            if np == last:
                continue
            dfs(cur, np)
        
dfs(-1, 0)

print(res)

Solution (Python):
import sys
def input():
    return sys.stdin.readline()[:-1]
import math
from itertools import permutations, combinations
from collections import defaultdict

sys.setrecursionlimit(10**7)
N, K = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(N-1)]
mod = 10**9+7

edges = [[] for _ in range(N)]
for abi in ab:
    a, b = abi[0], abi[1]
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)

max_edges = max(list(map(len, edges)))
nCr = {}
def cmb(n, r):
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n,r) in nCr: return nCr[(n,r)]
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)]


res = K
def dfs(last, cur):
    global res

    if last == -1:
        for i, np in enumerate(edges[0]):
            res *= (K-i-1)
            res %= mod
            dfs(0, np)

    else:
        num_edges_cur = len(edges[cur]) - 1
        if num_edges_cur == 0:
            return
        i = 0
        for i in range(K-2, K-num_edges_cur-2, -1):
            res *= i
            res %= mod
        for np in edges[cur]:
            if np == last:
                continue
            else:
                dfs(cur, np)
        
dfs(-1, 0)

print(res)

Solution (Python):

def permutation(n,i,mod):
    count = 1
    for _ in range(i):
        count = count * n % mod
        n -= 1
    return count

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N, K = map(int,input().split())
MOD = 10**9 + 7


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

V = [[] for _ in range(N)]
for a,b in ab:
    V[a].append(b)
    V[b].append(a)


def dfs(now, before):
    count = 0
    for after in V[now]:
        if after == before:
            continue
        count += 1
        dfs(after, now)
    if count == 0:
        return
    else:
        child[now] = count

child = [0] * N
dfs(0,0)

answer = 1
for i in range(N):
    if i == 0:
        answer *= permutation(K-1, child[i], MOD)
    else:
        answer *= permutation(K-2, child[i], MOD)
    answer %= MOD

print(answer * K % MOD)

Solution (Python):
import sys
sys.setrecursionlimit(10000000)
n,k=map(int,input().split())
graph=[[] for i in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  graph[a-1].append(b-1)
  graph[b-1].append(a-1)
MOD=10**9+7
def coloring(node,pre):
  if len(graph[node])>k:
    return 0
  if pre==-1:
    color=k-1
  else:
    color=k-2
  ans=1
  for i in graph[node]:
    if i==pre:continue
    ans*=color
    ans%=MOD
    color-=1
  for i in graph[node]:
    if i==pre:continue
    ans*=coloring(i,node)
    ans%=MOD
  return ans
print((k*coloring(0,-1))%MOD)

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()

class modfact(object):
    def __init__(self,n):
        fact=[1]*(n+1); invfact=[1]*(n+1)
        for i in range(1,n+1): fact[i]=i*fact[i-1]%MOD
        invfact[n]=pow(fact[n],MOD-2,MOD)
        for i in range(n-1,-1,-1): invfact[i]=invfact[i+1]*(i+1)%MOD
        self.__fact=fact; self.__invfact=invfact

    def inv(self,n):
        assert(n>0)
        return self.__fact[n-1]*self.__invfact[n]%MOD

    def fact(self,n):
        return self.__fact[n]

    def invfact(self,n):
        return self.__invfact[n]

    def comb(self,n,k):
        if(k<0 or n<k): return 0
        return self.__fact[n]*self.__invfact[k]*self.__invfact[n-k]%MOD

    def perm(self,n,k):
        if(k<0 or n<k): return 0
        return self.__fact[n]*self.__invfact[n-k]%MOD

def resolve():
    n,k=map(int,input().split())
    E=[[] for _ in range(n)]
    for _ in range(n-1):
        a,b=map(int,input().split())
        a-=1; b-=1
        E[a].append(b)
        E[b].append(a)

    ans=[k]
    mf=modfact(k)
    Q=[(0,-1)]
    while(Q):
        v,p=Q.pop()
        if(p==-1):
            ans[0]*=mf.perm(k-1,len(E[v]))
            ans[0]%=MOD
        else:
            ans[0]*=mf.perm(k-2,len(E[v])-1)
            ans[0]%=MOD
        for nv in E[v]:
            if(nv==p): continue
            Q.append((nv,v))

    print(ans[0])
resolve()

Solution (Python):
from collections import Counter,defaultdict,deque
import sys
import copy
from itertools import permutations, combinations
from heapq import heappop, heappush

sys.setrecursionlimit(10**8)
mod = 10**9+7
    
def inp(): 
    return int(input())
def inpm(): 
    return map(int,input().split())
def inpl(): 
    return list(map(int, input().split()))
def inpls(): 
    return list(input().split())
def inplm(n): 
    return list(int(input()) for _ in range(n))
def inpll(n): 
    return sorted([list(map(int, input().split())) for _ in range(n)])

def extgcd(a,b): 
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    return [w[0],w[1]]

def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return ( m + x%m ) % m
    
def nPk(n,k):
    res = 1
    for i in range(n,n-k,-1):
        res = (res*i)%mod
    return res

def main():
    n,k=inpm()
    g=[[] for _ in range(n)]
    for _ in range(n-1):
        a,b=inpm()
        a-=1
        b-=1
        g[a].append(b)
        g[b].append(a)
    ans=k
    did = [False for _ in range(n)]
    did[0] = True
    que = copy.copy(g[0])
    for i in g[0]:
        did[i]=True
    ans = (ans*nPk(k-1,len(que)))%mod
    while len(que)>0:
        go=que.pop()
        ans=(ans*nPk(k-2,len(g[go])-1))%mod
        for i in g[go]:
            if did[i]:
                continue
            did[i]=True
            que.append(i)
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque

N,K = map(int, input().split())
E = [[] for _ in range(N)]
for _ in range(N-1):
    a,b = map(int, input().split())
    E[a-1].append(b-1)
    E[b-1].append(a-1)
    
mod = 10**9+7
L = [0]*N
L[0] = K
ans = 1
q = deque()
q.append(0)
while q:
    t = q.popleft()
    c = max(K-1, L[t])
    for e in E[t]:
        if L[e] == 0:
            c -= 1
            if c <= 0:
                ans = 0
                q = []
                break
            L[e] = c
            q.append(e)
            
for i in range(N):
    ans *= L[i]
    ans %= mod
    
print(ans)

Solution (Python):
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)

n,k=map(int,input().split())
l=[[] for _ in range(n)]
ans=k
for _ in range(n-1):
    a,b=map(int,input().split())
    a-=1; b-=1
    l[a].append(b)
    l[b].append(a)

mod=10**9+7
fact=[1]
fact_inv=[1]
for i in range(10**5+1):
    new_fact=fact[-1]*(i+1)%mod
    fact.append(new_fact)
    fact_inv.append(pow(new_fact,mod-2,mod))

def mod_p(n,k,mod):
    if n-k<0:
        print(0)
        exit()
    return fact[n]*fact_inv[n-k]%mod

def dfs(v,p):
    ans2=1
    for a in l[v]:
        if a==p:
            continue
        ans2*=dfs(a,v)
        ans2%=mod
    return mod_p(k-2,len(l[v])-1,mod)*ans2%mod

ans*=mod_p(k-1,len(l[0]),mod)

for a in l[0]:
    ans*=dfs(a,0)

print(ans%mod)

Solution (Python):
import sys
from collections import deque
n, k = [int(i) for i in sys.stdin.readline().split()]
ls = []
graph = {i:[] for i in range(n)}
for i in range(n-1):
    a, b = [int(i) for i in sys.stdin.readline().split()]
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)
    ls.append((a, b))
MOD = 10**9+7
root = 0
que = deque([root])
colors = [-1 for i in range(n)]
parent = [-1 for i in range(n)]
grandpa = [-1 for i in range(n)]
already = {root}
res = k
while len(que) > 0:
    cur = que.popleft()
    cnt = 0
    for _next in graph[cur]:
        if _next == parent[cur]:
            continue
        parent[_next] = cur
        grandpa[_next] = parent[cur]
        que.append(_next)
        if parent[cur] != -1:
            res = res * (k - cnt - 2) % MOD
        else:
            res = res * (k - cnt - 1) % MOD
        cnt += 1
print(res)

Solution (Python):
from collections import deque
N, K = map(int, input().split())

if N == 1:
    print(K)

G = {k: [] for k 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

ans = 1
for i in range(1, N+1):
    if len(G[i]) == 1:
        que = deque([(i, 0, 0, -1)])

        while que:
            ci, d1, d2, p = que.popleft()
            ans *= max(0, K-d1-d2)
            ans %= mod
            

            c = 0
            for ni in G[ci]:
                if ni != p:
                    que.append((ni, 1, d1+c, ci))
                    c += 1

        print(ans)
        exit()

Solution (Python):
import sys
sys.setrecursionlimit(10**5)
n, k = map(int, input().split())
mod = 10 ** 9 + 7
adjacent_list = [[] for i in range(n+1)]
for i in range(n - 1):
    a, b = map(int, input().split())
    adjacent_list[a].append(b)
    adjacent_list[b].append(a)
finished = set([1])
ans = k
def dfs(current, finished,num):
    global ans
    global k
    unsearched = set(adjacent_list[current]) - finished
    num = max(k - 1, num)
    if len(unsearched) == 0:
        return
    for i in unsearched:
        finished.add(i)
        num -= 1
        ans *= num
        ans %= mod
        dfs(i,finished, num)
dfs(1,finished,k)
print(ans)

Solution (Python):
import sys

sys.setrecursionlimit(100000)

def dps(u,p,c):
  x[c]= u
  u = k-(1 if p<0 else 2)
  for i in range(len(l[c])):
    if l[c][i]!=p:
      if u>0:
        dps(u,c,l[c][i])
        u-=1
      else:
        break
  return

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

l=[[] for i in range(n)]
x=[0]*n

for i in range(n-1):
  a,b= map(int,input().split())
  l[a-1].append(b-1)
  l[b-1].append(a-1)

dps(k,-1,0)

t=1
for i in range(n):
  t=(t*x[i])%(10**9+7)

print(t)

Solution (Python):
n,k=[int(j) for j in input().split()]
l=[[] for i in range(n)]

for i in range(n-1):
    a,b=[int(j)-1 for j in input().split()]
    l[a].append(b)
    l[b].append(a)

s=set([0])
ans=k
mod=10**9+7
from collections import deque
q=deque([(0,k-1)])
while q:
    x,y=q.popleft()
    j=0
    for i in l[x]:
        if i in s:
            continue
        s.add(i)
        if y-j<=0:
            print(0)
            exit()
        ans*=y-j
        ans=ans%mod
        q.append((i,k-2))
        j+=1
print(ans)

Solution (Python):
n,k=[int(j) for j in input().split()]
l=[[] for i in range(n)]

for i in range(n-1):
    a,b=[int(j)-1 for j in input().split()]
    l[a].append(b)
    l[b].append(a)

s=set([0])
ans=k
mod=10**9+7
from collections import deque
q=deque([(0,k-1)])
while q:
    x,y=q.popleft()
    j=0
    for i in l[x]:
        if i in s:
            continue
        s.add(i)
        if y-j<=0:
            print(0)
            exit()
        ans*=y-j
        ans=ans%mod
        q.append((i,k-2))
        j+=1
print(ans)