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 
from collections import deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N, K = map(int, readline().split())
MOD = 10**9+7
graph = [[] for _ in range(N+1)]

for _ in range(N-1):
    a,b = map(int,readline().split())
    graph[a].append(b)
    graph[b].append(a)

dist = [-1]*(N+1)
dist[1] = K
q = deque([1])

def bfs():
    while q:
        x = q.popleft()
        if dist[x] == K:
            cnt = 1
        else:
            cnt = 2
        for nx in graph[x]:
            if dist[nx] != -1:
                continue
            dist[nx] = max(0,K-cnt)
            q.append(nx)
            cnt += 1
            
bfs()
ans = 1
for i in range(1,N+1):
    ans *= dist[i]
    ans %= MOD      
print(ans)

Solution (Python):
from collections import deque

def permutation(n, r):
    if (r < 0) or (n < r):
        return 0

    res = factinv[r] % p
    for i in range(r):
        res = res * (n - i) % p

    return fact[n] * factinv[n-r] % p

def BFS(tree, root):
    N = len(tree)
    dist = [-1]*N

    res = K

    q = deque([root])
    dist[root] = 0

    while q:
        v = q.popleft()
        for n_v in tree[v]:
            if dist[n_v] != -1:
                continue
            dist[n_v] = dist[v] + 1
            q.append(n_v)
        
        child_cnt = len(tree[v])
        if dist[v] > 0:
            child_cnt -= 1

        if child_cnt > 0:
            color = K - 1
            if dist[v] > 0:
                color -= 1
            
            if color < child_cnt:
                res = 0
                break
            else:
                res *= permutation(color, child_cnt)
                res %= p
    
    return res

N, K = map(int, input().split())
tree = [[] for _ in range(N)]

p = 10 ** 9 + 7

fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]
 
for i in range(2, K + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

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

print(BFS(tree, 0))

Solution (Python):
def main():
    import sys
    sys.setrecursionlimit(311111)
    import numpy as np
    ikimasu = sys.stdin.buffer.readline
    ini = lambda: int(ins())
    ina = lambda: list(map(int, ikimasu().split()))
    ins = lambda: ikimasu().strip()
    n,k = ina()
    tmp = [[] for _ in range(n)]
    for _ in range(n-1):
        x,x1=  ina()
        x-=1
        x1-=1
        tmp[x].append(x1)
        tmp[x1].append(x)
    def dfs(teiru,ta):
        rick = 1
        coulduse = k-1 if ta==-1 else k-2
        for i in tmp[teiru]:
            if i == ta:
                continue
            rick*=coulduse
            rick%=1000000007
            coulduse-=1
            rick*=dfs(i,teiru) 
            rick%=1000000007
        return rick
    print(k*dfs(0,-1)%1000000007)
    

    


        
        
        


    
        


        


    




















if __name__ == "__main__":
    main()

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

n,k=map(int,input().split())
m=10**9+7
to=[[] for i in range(n)]
for i in range(n-1):
  a,b=map(lambda x:int(x)-1, input().split())
  to[a].append(b)
  to[b].append(a)
frac=[1]*(10**5+1)
for i in range(1,10**5+1):
  frac[i]=frac[i-1]*i
  frac[i]%=m


def nPk(_n,_k):
  if _n<0 or _k<0 or _n-_k<0: return 0;
  a=frac[_n]
  b=frac[_n-_k]
  return (a*pow(b,m-2,m))%m


def dfs(_v, _u=-1):
  global ans
  for u in to[_v]:
    if u==_u: continue
    dfs(u, _v)
  p=len(to[_v])
  ans*=nPk(k,p+1) if _v==0 else nPk(k-2,p-1)
  ans%=m
    
    
ans=1
chk=[False]*n
dfs(0)
  
print(ans)

Solution (Python):
import sys
from collections import deque

mod = 10**9 + 7
input = sys.stdin.readline
N, K = map(int, input().split())

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

q = deque()
q.append((0, K, 0))

dp = 1
visited = set()
while q:
    node, count, d = q.popleft()
    if node in visited:
        continue
    dp *= count
    dp %= mod
    visited.add(node)

    res = K
    if d == 0:
        res -= 1
    else:
        res -= 2
    for n_node in paths[node]:
        if n_node not in visited:
            
            q.append((n_node, res, d+1))
            res -= 1

print(dp)

Solution (Python):

from collections import deque
N,K=map(int,input().split())
p=10**9+7
G=[[] for _ in [0]*(N+1)]
for _ in [0]*(N-1):
    a,b=map(int,input().split())
    G[a].append(b)
    G[b].append(a)
    
D=[-1]*(N+1)
F=set()
color=[K]*(N+1)

res=1
D[1]=0
q=deque()
q.append(1)
while q:
    node=q.pop()
    if node in F:
        continue
    if D[node]>1:
        color[node]-=1
    if color[node]<=0:
        res*=0
    else:
        res=(res*color[node])%p
    F.add(node)
    i=1
    for next_node in G[node]:
        if D[next_node]>=0:
            continue
        D[next_node]=D[node]+1
        color[next_node]-=i
        i+=1
        q.append(next_node)
print(res%p)

Solution (Python):
import sys

input = sys.stdin.readline
N, K = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(N - 1)]
P = int(1e9+7)
if N == 1:
    print(K % P)
    sys.exit(0)
kaizyo = [0]
kaizyo_inv = [0]
tmp = 1
for i in range(1, K+1):
    tmp = (tmp*i) % P
    kaizyo.append(tmp)
    kaizyo_inv.append(pow(tmp, P - 2, P))


def comb(n, r):
    if n < r or n < 0:
        return 0
    elif n == r or r == 0:
        return 1
    else:
        return kaizyo[n] * kaizyo_inv[r] * kaizyo_inv[n - r]


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

children = [[] for _ in range(N)]
q = [(0, None)]
while len(q) > 0:
    v, p = q.pop()
    for u in g[v]:
        if u != p:
            q.append((u, v))
            children[v].append(u)

if len(children[0]) > K - 1:
    print(0)
    sys.exit()
ans = 1
ans *= K
n_child = len(children[0])
ans = (ans * comb(K - 1, n_child)*kaizyo[n_child]) % P
q = [i for i in children[0]]
while len(q) > 0:
    v = q.pop()
    n_child = len(children[v])
    if n_child > K - 2:
        print(0)
        sys.exit()
    if n_child != 0:
        ans = (ans * comb(K - 2, n_child)*kaizyo[n_child]) % P
    q += children[v]
print(ans)

Solution (Python):
from collections import deque

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

  def bfs(s):
      seen = [0]*N
      color = [0]*N
      todo = deque()
      seen[s]=1
      todo.append(s)
      color[s]=K
      while todo:
        a = todo.popleft()
        if a == s: count = K-1
        else: count = K-2
        for b in G[a]:
          if seen[b] == 0:
            seen[b] = 1
            todo.append(b)
            color[b] = count %mod
            count -= 1
      return color

  MAX,start = 0,-1
  for i in range(N):
    if len(G[i])>MAX:
      MAX=len(G[i])
      start = i
  
  color = bfs(start)
  ans = 1
  for i in range(N):
    ans *= color[i]
    ans %= mod

  print(ans)
  
if __name__=="__main__":
  main()

Solution (Python):
from collections import deque

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

def bfs(s):
    seen = [0]*N
    prev = [0]*N
    color = [0]*N
    todo = deque()
    seen[s]=1
    todo.append(s)
    color[s]=K
    while todo:
      a = todo.popleft()
      if a == start: count = K-1
      else: count = K-2
      for b in G[a]:
        if seen[b] == 0:
          seen[b] = 1
          todo.append(b)
          prev[b] = a
          color[b] = count %mod
          count -= 1
    return color
  
MAX,start = 0,-1
for i in range(N):
  if len(G[i])>MAX:
    MAX=len(G[i])
    start = i
    
color = bfs(start)
ans = 1
for i in range(N):
  ans *= color[i]
  ans %= mod
  
print(ans)

Solution (Python):
mod = 10 ** 9 + 7
import sys
sys.setrecursionlimit(10 ** 7)
def dfs(u):
    cnt = 0
    res = 1
    for i in edges[u]:
        if visited[i] == -1:
            visited[i] = 0
            cnt += 1
            res *= dfs(i)
            res %= mod
    for i in range(cnt):
        res *= k - i - 2
        res %= mod
    return res
n, k = map(int, input().split())
edges = [[] for i in range(n)]
for i in range(n - 1):
    a, b = map(int, input().split())
    edges[a - 1].append(b - 1)
    edges[b - 1].append(a - 1)
visited = [-1] * n
visited[0] = 0
ans = k
for i in range(len(edges[0])):
    ans *= (k - i - 1)
    ans %= mod
for i in edges[0]:
    visited[i] = 0
    ans *= dfs(i)
    ans %= mod
print(ans)

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

mod = 10**9 + 7
INF = float("inf")

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

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


dq = deque([0])




color = [INF] * N
color[0] = K

"""
root = 0 から末端に向かって調べる

子1, 子2, 子3, ...と複数の「未着色」の子がある場合、塗ることが出来る色の数は
K-1, K-2, K-3,... (p==0 の場合)
K-2, K-3, K-4,... (p!=0 の場合)　のようになる

子が十分多い場合、どこかで「0」になるので、ans = 0　となる
故に、色の数が負になっても答えには影響しない
"""

while dq:
    
    p = dq.popleft()
    
    cnt = 0
    for c in edges[p]:
        if color[c] == INF:
            if p == 0:
                color[c] = (K - 1 - cnt) % mod
            else:
                color[c] = (K - 2 - cnt) % mod
            cnt += 1
            dq.append(c)

ans = 1
for i in range(N):
    ans = (ans * color[i]) % mod

print(ans)

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

mod = 10**9 + 7
INF = float("inf")

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

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


dq = deque([0])




color = [INF] * N
color[0] = K

"""
root = 0 から末端に向かって調べる

子1, 子2, 子3, ...と複数の「未着色」の子がある場合、塗ることが出来る色の数は
K-1, K-2, K-3,... (p==0 の場合)
K-2, K-3, K-4,... (p!=0 の場合)　のようになる

子が十分多い場合、どこかで「0」になるので、ans = 0　となる
故に、色の数が負になっても答えには影響しない
"""

while dq:
    
    p = dq.popleft()
    
    cnt = 0
    for c in edges[p]:
        if color[c] == INF:
            if p == 0:
                color[c] = (K - 1 - cnt) % mod
            else:
                color[c] = (K - 2 - cnt) % mod
            cnt += 1
            dq.append(c)

ans = 1
for i in range(N):
    ans = (ans * color[i]) % mod

print(ans)

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


mod = 10**9 + 7
INF = 10**6
N, K = map(int, input().split())
edges = [[] * N for _ in range(N)]
for _ in range(N - 1):
    a, b = map(lambda x: int(x) - 1, input().split())
    edges[a].append(b)
    edges[b].append(a)
dq = deque([0])
color = [INF] * N
color[0] = K
ans = K
while dq:
    p = dq.popleft()
    cnt = 0
    for c in edges[p]:
        if color[c] == INF:
            if p == 0:
                color[c] = (K - 1 - cnt) % mod
            else:
                color[c] = (K - 2 - cnt) % mod
            ans = (ans * color[c]) % mod
            cnt += 1
            dq.append(c)
print(ans)

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

mod = 10**9 + 7
INF = 10**6

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

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


dq = deque([0])




color = [INF] * N
color[0] = K

"""
root = 0 から末端に向かって調べる

子1, 子2, 子3, ...と複数の「未着色」の子がある場合、塗ることが出来る色の数は
K-1, K-2, K-3,... (p==0 の場合)
K-2, K-3, K-4,... (p!=0 の場合)　のようになる

子が十分多い場合、どこかで「0」になるので、ans = 0　となる
故に、色の数が負になっても答えには影響しない
"""
ans = K

while dq:
    
    p = dq.popleft()
    
    cnt = 0
    for c in edges[p]:
        if color[c] == INF:
            if p == 0:
                color[c] = (K - 1 - cnt) % mod
            else:
                color[c] = (K - 2 - cnt) % mod
            ans = (ans * color[c]) % mod
            cnt += 1
            dq.append(c)

print(ans)

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

mod = 10**9 + 7
INF = float("inf")

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

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


dq = deque([0])




color = [INF] * N
color[0] = K

"""
root = 0 から末端に向かって調べる

子1, 子2, 子3, ...と複数の「未着色」の子がある場合、塗ることが出来る色の数は
K-1, K-2, K-3,... (p==0 の場合)
K-2, K-3, K-4,... (p!=0 の場合)　のようになる

子が十分多い場合、どこかで「0」になるので、ans = 0　となる
故に、色の数が負になっても答えには影響しない
"""
ans = K

while dq:
    
    p = dq.popleft()
    
    cnt = 0
    for c in edges[p]:
        if color[c] == INF:
            if p == 0:
                color[c] = (K - 1 - cnt) % mod
            else:
                color[c] = (K - 2 - cnt) % mod
            ans = (ans * color[c]) % mod
            cnt += 1
            dq.append(c)

print(ans)

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

mod = 10**9 + 7
INF = float("inf")

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

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


dq = deque([0])




color = [INF] * N
color[0] = K

"""
root = 0 から末端に向かって調べる

子1, 子2, 子3, ...と複数の「未着色」の子がある場合、塗ることが出来る色の数は
K-1, K-2, K-3,... (p==0 の場合)
K-2, K-3, K-4,... (p!=0 の場合)　のようになる

子が十分多い場合、どこかで「0」になるので、ans = 0　となる
故に、色の数が負になっても答えには影響しない
"""

while dq:
    
    p = dq.popleft()
    
    cnt = 0
    for c in edges[p]:
        if color[c] == INF:
            if p == 0:
                color[c] = (K - 1 - cnt) % mod
            else:
                color[c] = (K - 2 - cnt) % mod
            cnt += 1
            dq.append(c)

ans = 1
for i in range(N):
    ans = (ans * color[i]) % mod

print(ans)

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

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

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


dq = deque([0])

visited = [False] * N
visited[0] = True



color = [0] * N
color[0] = K

"""
root = 0 から末端に向かって調べる

子1, 子2, 子3, ...と複数の「未着色」の子がある場合、塗ることが出来る色の数は
K-1, K-2, K-3,... (p==0 の場合)
K-2, K-3, K-4,... (p!=0 の場合)　のようになる

子が十分多い場合、どこかで「0」になるので、ans = 0　となる
故に、色の数が負になっても答えには影響しない
"""

while dq:
    
    p = dq.popleft()
    
    cnt = 0
    for c in edges[p]:
        if not visited[c]:
            if p == 0:
                color[c] = (K - 1 - cnt) % mod
            else:
                color[c] = (K - 2 - cnt) % mod
            cnt += 1
            visited[c] = True
            dq.append(c)

ans = 1
for i in range(N):
    ans = (ans * color[i]) % mod

print(ans)

Solution (Python):
from collections import deque


class ModCalc:
    mod = 10**9 + 7

    def __init__(self, n):
        self.n = n
        self.inv = [1] * (self.n + 1)
        self.fac = [1] * (self.n + 1)
        self.finv = [1] * (self.n + 1)
        self.inv[0] = 0
        self.inv_table()

    def inv_table(self):
        for i in range(2, self.n+1):
            self.inv[i] = self.inv[self.mod % i] * (self.mod - self.mod // i) % self.mod
            self.fac[i] = self.fac[i-1] * i % self.mod
            self.finv[i] = self.finv[i-1] * self.inv[i] % self.mod

    def comb(self, n, r):
        if n < r:
            return 0
        if n < 0 or r < 0:
            return 0

        return self.fac[n] * self.finv[r] % self.mod * self.finv[n-r] % self.mod

    def perm(self, n, r):
        if n < r:
            return 0
        if n < 0 or r < 0:
            return 0

        return self.fac[n] * self.finv[n-r] % self.mod

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


n, k = map(int, input().split())
tree = [[] for _ 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
mod = 10**9 + 7
mc = ModCalc(100001)

q = deque([1])
dist = [-1] * (n+1)
dist[1] = 0
while q:
    now = q.popleft()
    cnt = 0
    for node in tree[now]:
        if dist[node] != -1:
            continue
        cnt += 1
        q.append(node)
        dist[node] = dist[now] + 1

    if dist[now] == 0:
        ans *= mc.comb(k-1, cnt) * mc.fact(cnt) % mod
        ans %= mod
    else:
        ans *= mc.comb(k-2, cnt) * mc.fact(cnt) % mod
        ans %= mod

print(ans)

Solution (Python):
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
import itertools
import heapq as hq
import sys
def gtr(n):
    tree = [[] for i in range(n)]
    for i in range(n-1):
        u,v =ma()
        tree[u-1].append(v-1)
        tree[v-1].append(u-1)
    return tree
mod=10**9+7
n,k =ma()
tree = gtr(n)
stack = collections.deque()
stack.append(0)
visited=[True]+[False]*(n-1)
col = [k]*n
while stack:
    s = stack.pop()
    if s==0:
        cnt=k-1
    else:
        cnt=k-2
    for node in tree[s]:
        if not visited[node]:
            visited[node]=True
            stack.append(node)
            col[node]= max(0,cnt)
            cnt-=1
ans=1
for c in col:
    ans=ans*c%mod
print(ans)

Solution (Python):
from collections import deque
mod = 10**9 + 7
n, k = map(int, input().split())
edges = [[]*n for _ in range(n)]
for _ in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    edges[a].append(b)
    edges[b].append(a)

root = 0
d = deque([root])
visited = [False]*n
visited[root] = True
colored = [-1]*n
colored[root] = k
while d:
    p = d.pop()
    count = 0
    for c in edges[p]:
        if visited[c]:
            continue
        visited[c] = True
        d.append(c)
        if p == root:
            colored[c] = (k-1-count) % mod
        else:
            colored[c] = (k-2-count) % mod
        count += 1
ans = 1
for i in range(n):
    ans = ans*colored[i] % mod
print(ans)

Solution (Python):
from collections import deque
mod = 10**9 + 7
n, k = map(int, input().split())



class UnionFind:
    def __init__(self, n):
        self.par = [-1]*(n+1)  
        self.rank = [0]*(n+1)

    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.find(self.par[x])  
            return self.par[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return
        else:
            if self.rank[x] < self.rank[y]:
                self.par[y] += self.par[x]
                self.par[x] = y
            else:
                self.par[x] += self.par[y]
                self.par[y] = x
                if self.rank[x] == self.rank[y]:
                    self.rank[x] += 1

    def same_check(self, x, y):
        return self.find(x) == self.find(y)  

    def size(self, x):
        return -self.par[self.find(x)]


edges = [[]*n for _ in range(n)]
UF = UnionFind(n)
for _ in range(n-1):
    a, b = map(int, input().split())
    UF.union(a, b)
    a -= 1
    b -= 1
    edges[a].append(b)
    edges[b].append(a)

root = UF.find(1)

root -= 1
d = deque([root])
visited = [False]*n
visited[root] = True
colored = [-1]*n
colored[root] = k
while d:
    p = d.pop()
    count = 0
    for c in edges[p]:
        if visited[c]:
            continue
        visited[c] = True
        d.append(c)
        if p == root:
            colored[c] = (k-1-count) % mod
        else:
            colored[c] = (k-2-count) % mod
        count += 1
ans = 1
for i in range(n):
    ans = ans*colored[i] % mod
print(ans)

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




def RD(): return input().rstrip().decode()
def II(): return int(input())
def FI(): return float(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))


from collections import deque

def main():
	mod=10**9+7
	n,k=MI()
	G=[[] for _ in range(n+1)]

	for _ in range(n-1):
		a,b=MI()
		G[a].append(b)
		G[b].append(a)
	

	ans=k

	for i in range(len(G[1])):
		ans*=k-i-1
		ans%=mod
	

	Q=deque(G[1])
	

	sumi=set([1]+G[1])
	


	while Q:
		now=Q.popleft()
		kk=k-2
		for i in G[now]:
			if i not in sumi:
				ans*=kk
				ans%=mod
				kk-=1
				sumi.add(i)
				Q.append(i)

	print(ans%mod)


























if __name__ == "__main__":
	main()

Solution (Python):
from collections import defaultdict, deque

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

neighbor = defaultdict(list)

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

d = deque([(0, -1)])

ans = K
mod = 10**9 + 7
while d:
    cur, par = d.pop()

    i = 1 if par == -1 else 2
    for n in neighbor[cur]:
        if n != par:
            d.append((n, cur))
            ans *= (K-i)
            ans %= mod
            i += 1

print(ans)

Solution (Python):
from collections import deque

n,k=map(int,input().split())
visited=[False]*n
visited[0]=True
color=[0]*n
color[0]=k
mod=10**9+7

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)


Q=deque()
Q.append((0))
ans=k

while Q:
  p=Q.popleft()
  cnt=0
  for i in graph[p]:
    if visited[i]==False:
        cnt+=1
        Q.append((i))
        visited[i]=True

  if p==0:
      for i in range(cnt):
          ans*=k-i-1
          ans%=mod

  else:
      for i in range(cnt):
          ans*=k-i-2
          ans%=mod


print(ans%mod)

Solution (Python):
from collections import deque

n,k=map(int,input().split())
visited=[False]*n
visited[0]=True
color=[0]*n
color[0]=k
mod=10**9+7

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)


Q=deque()
Q.append((0))
ans=k

while Q:
  p=Q.pop()
  cnt=0
  for i in graph[p]:
    if visited[i]==False:
        cnt+=1
        Q.append((i))
        visited[i]=True

  if p==0:
      for i in range(cnt):
          ans*=k-i-1
          ans%=mod

  else:
      for i in range(cnt):
          ans*=k-i-2
          ans%=mod


print(ans%mod)

Solution (Python):

import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from fractions import Fraction
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations, accumulate
from operator import add, mul, sub, itemgetter, attrgetter


import sys


readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(readline())


def read_int_n():
    return list(map(int, readline().split()))


def read_float():
    return float(readline())


def read_float_n():
    return list(map(float, readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def ep(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.perf_counter()
        ret = f(*args, **kwargs)
        e = time.perf_counter()

        ep(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, K, AB):
    g = defaultdict(list)
    for a, b in AB:
        g[a].append(b)
        g[b].append(a)

    s = [(1, -1, 0, 0)]
    ans = [1] * (N+1)
    while s:
        u, p, k1, k2 = s.pop()
        ans[u] = K - k1 - k2

        cu = 0
        for v in g[u]:
            if v == p:
                continue
            s.append((v, u, 1, cu+k1))
            cu += 1

    M = 10**9+7
    return reduce(lambda x, y: (x * y) % M, ans)



def main():
    N, K = read_int_n()
    AB = [read_int_n() for _ in range(N-1)]
    print(slv(N, K, AB))


if __name__ == '__main__':
    main()

Solution (Python):
N, K = map(int, input().split())
mod = 1000000007

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)


counts = [False]*N

q = [0]
counts[0] = True
ans = K
while q:
  i = q.pop(0)
  
  js = E[i]
  if i == 0:
    c = K - 1
  else:
    c = K - 2
  for j in js:
    if not(counts[j]):
      counts[j] = True
      ans = (ans * c) % mod
      c -= 1
      q.append(j)

print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(200000)

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


def dfs(cur,p,nei):
    
    
    
    res = K-nei 
    nxnei = min(nei+1,2)
    for nx in edges[cur]:
        if nx != p:
            res = res * dfs(nx,cur,nxnei) % mod
            nxnei += 1
    return res

print(dfs(1,0,0))

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
N,K = map(int,input().split())
edges = [[] for _ in range(N)]
used = [False]*N
mod = 10**9+7
for _ in range(N-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    edges[a].append(b)
    edges[b].append(a)
def f(n,c):
    sm = 1
    t = K-c
    for m in edges[n]:
        if not used[m]:
            used[m] = True
            if t <= 0:
                print(0)
                exit(0)
            sm = (sm*f(m,2)*t) % mod
            t -= 1
    return sm
used[0] = True
print(K*f(0,1) % mod)

Solution (Python):
import sys
import collections

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007



def main():
	
	n, k = tin()
	
	tree = [[] for _ in range(n)]
	for _ in range(n-1):
		a, b = tin()
		tree[a-1].append(b-1)
		tree[b-1].append(a-1)
	
	ret = k
	qq = collections.deque()
	qq.append([0, -1])
	opened = set()
	opened.add(0)
	while qq:
		pos, parent = qq.popleft()
		i=0
		for np in tree[pos]:
			if np == parent:
				continue
			qq.append((np, pos))
			
			add = 0
			if parent == -1:
				add = 1
			
			ret *= k-i-2+(add)
			ret %= mod
			i+=1
			
			
	print(ret)
		
	
	
	

isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		
			
	ret = main()
	if ret is not None:
		print(ret)

Solution (Python):
'''
自宅用PCでの解答
'''
import math

import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7

dir = [(-1,0),(0,-1),(1,0),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"
INF = 1<<32-1


def main():
    n,k = map(int,ipt().split())
    if n == 1:
        print(k)
        exit()
    d = [True]*(n+1)
    v = [k-2]*(n+1)
    ans = k*(k-1)
    for i in range(n-1):
        a,b = map(int,ipt().split())
        if d[a]:
            d[a] = False
        else:
            ans *= v[a]
            ans %= mod
            v[a] -= 1
        a = b
        if d[a]:
            d[a] = False
        else:
            ans *= v[a]
            ans %= mod
            v[a] -= 1

    print(ans)

    return None

if __name__ == '__main__':
    main()

Solution (Python):
n,k = map(int,input().split())
mod = 10**9+7
g = [[] for _ in range(n)]
for _ in range(n-1):
    a,b = map(int,input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)
from collections import deque
stack = deque([(0,k)])
seen = [True]*n
seen[0] = False

ans = 1

while stack:
    u,t = stack.popleft()
    ans = (ans*t)%mod
    if u==0: l = k-1
    else: l = k-2
    for v in g[u]:
        if seen[v]:
            seen[v] =False
            stack.append((v,l))
            l -=1
print(ans)

Solution (Python):
import collections

n, k = map(int, input().split())
mod = 10 ** 9 + 7
graph = [[] for i in range(n + 1)]
for i in range(n - 1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
flag = [False for i in range(n + 1)]
flag[1] = True
queue = collections.deque([1])
ans = k
while queue:
    test = queue.popleft()
    temp = [flag[graph[test][i]] for i in range(len(graph[test]))].count(True)
    num = 0
    for i in range(len(graph[test])):
        if flag[graph[test][i]] == True:
            continue
        ans *= (k - temp - num - 1)
        ans %= mod
        num += 1
        queue.append(graph[test][i])
        flag[graph[test][i]] = True
print(ans)

Solution (Python):
n,k=map(int,input().split())
e=[[] for i in range(n)]
for i in range(n-1):
  a,b=map(lambda x:int(x)-1,input().split())
  e[a].append(b)
  e[b].append(a)

d=[-1 for i in range(n)]
c=[0 for i in range(n)]
m=[-1 for i in range(n)]
d[0]=0
s=[0]
while s:
  ns=[]
  for i in s:
    for j in e[i]:
      if d[j]!=-1:
        continue
      ns.append(j)
      m[j]=i
      c[i]+=1
      d[j]=d[i]+1
  s=ns

mod=10**9+7
frac=[1]
for i in range(1,10**5):
  frac.append((frac[-1]*i)%mod)

r=k
for i in range(n):
  if c[i]==0:
    continue
  if d[i]==0:
    if k-1-c[i]<0:
      r=0
      break
    r=(r*frac[k-1]*pow(frac[k-1-c[i]],mod-2,mod))%mod
  else:
    if k-2-c[i]<0:
      r=0
      break
    r=(r*frac[k-2]*pow(frac[k-2-c[i]],mod-2,mod))%mod
print(r)

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readlines

from collections import deque

def main():

    lines = input()
    n, k = list(map(int, lines[0].split()))
    a = [[] for i in range(n+1)]

    for i in range(1, n):
        r, l = list(map(int, lines[i].split()))
        a[r].append(l)
        a[l].append(r)

    que = deque()
    que.append(1)
    colors = [-1] * (n+1)
    colors[1] = k
    ways = k

    while que:
        p = que.popleft()
        
        if p == 1:
            now_color = k
            for son in a[p]:
                now_color -= 1
                ways = (ways * now_color) % 1_000_000_007
                colors[son] = now_color
                que.append(son)
        else:
            now_color = k-1
            for son in a[p]:
                if colors[son] < 0:
                    now_color -= 1
                    colors[son] = now_color
                    ways = (ways * now_color) % 1_000_000_007
                    que.append(son)

    print(ways)

main()