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):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math

    
    mod = 10**9 + 7

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

    def dfs(v, par, k):
        if par == -1:
            kk = k-1
        else:
            kk = k-2

        res = 1
        if v == 0:
            res *= k

        for i in range(len(adj[v])):
            nv = adj[v][i]
            if  nv == par:
                continue
            res *= kk * dfs(nv, v, k)
            res %= mod
            kk -= 1
        return res

    res = dfs(0, -1, k)
    print(res)

if __name__ == '__main__':
    main()

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

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


def dfs(now, par, num):
    global ans
    ans *= num
    ans %= mod
    num = k - 1
    if par != -1:
        num -= 1
    for next in graph[now]:
        if next != par:
            dfs(next, now, num)
            num -= 1


dfs(0, -1, k)
print(ans)

Solution (Python):
from collections import deque

n,k = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(n-1)]
tree = [list() for i in range(n+1)]
visited = [0] * (n+1)
for a,b in ab:
  tree[a].append(b)
  tree[b].append(a)
visited[1] = 1
queue = deque([(1,0)])
ans = k
mod = 10 ** 9 + 7
while queue:
  vertex, depth = queue.popleft()
  res = k - min(depth+1,2)
  for NEXT in tree[vertex]:
    if not visited[NEXT]:
      visited[NEXT] = 1
      ans *= res
      ans %= mod
      res -= 1
      queue.append((NEXT,depth+1))
print(ans)

Solution (Python):

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


MAXN = K+5
fac = [1,1] + [0]*MAXN
finv = [1,1] + [0]*MAXN
inv = [0,1] + [0]*MAXN
for i in range(2,MAXN+2):
    fac[i] = fac[i-1] * i % MOD
    inv[i] = -inv[MOD%i] * (MOD // i) % MOD
    finv[i] = finv[i-1] * inv[i] % MOD
 
def nPr(n,r):
    if n < r:
        return 0
    return fac[n] * finv[n-r]
"""
curr とその親prevの色が決まっているときに、currの子nxtの色の塗り方の場合の数は
nPr(K-2, len(es[curr]) - 1)
Kのうちprevとcurrで２色使っていて、currにつながっているもののうち一つはprevだから、１引いたものが子供の数。
で、一番初めのノードoriginについて考えると、親はないのでノードorigin自体はK個の塗り方があり、その子には、nPr(K-1, len(es[origin]))の塗り方がある
あとはDFS的に子供の塗り方を決めていく

"""

checked = [False] * N
ans = K * nPr(K-1, len(es[0]))
checked[0] = True

stack = []
for nxt in es[0]:
    stack.append(nxt)

while stack:
    curr = stack.pop()
    checked[curr] = True
    ans *= nPr(K-2, len(es[curr]) - 1)
    if ans >= MOD: ans %= MOD
    for nxt in es[curr]:
        if not checked[nxt]:
            stack.append(nxt)

print(ans % MOD)

Solution (Python):
import math 
import sys 
"""
def p(n,r):
    if n<r:
        return 1
    return math.factorial(n)//math.factorial(n-r)
"""
def main():
    input=sys.stdin.readline 
    N,K=map(int,input().split())
    E=[[] for _ in range(N)]
    MOD = 10**9+7
    for _ in range(N-1):
        u,v=map(int,input().split())
        u-=1
        v-=1
        E[u].append(v)
        E[v].append(u)

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

    color = [-1 for _ in range(N)]
    dp = [-1 for _ in range(N)]
    stack = []
    color[u]=1
    ans=K
    for i,v in enumerate(E[u]):
        stack.append(v)
        ans*=(K-i-1)
        ans%=MOD


    while stack:
        u=stack.pop()
        color[u]=1
        length=0
        for v in E[u]:
            if color[v]==-1:
                stack.append(v)
                length+=1
        if dp[length]==-1:
            tmp=1
            for i in range(K-1-length,K-1):
                tmp*= i 
                tmp%=MOD 
            ans*=tmp 
        else:
            ans*=dp[length]
        ans%=MOD

    print(ans%MOD)

if __name__ == '__main__':
    main()

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

def P(n, r):
    res = 1
    
    for i in range(r):
        res *= n-i
        res %= MOD
    
    return res

def bfs():
    q = deque([0])
    visited = [False]*N
    visited[0] = True
    ans = K
    
    while q:
        v = q.popleft()
        cnt = 0
        
        for nv in G[v]:
            if not visited[nv]:
                cnt += 1
                visited[nv] = True
                q.append(nv)
        
        if v==0:
            ans *= P(K-1, cnt)
            ans %= MOD
        else:
            ans *= P(K-2, cnt)
            ans %= MOD
            
    return ans

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)

print(bfs())

Solution (Python):

"""
問題：
n頂点の木(辺の情報が与えられる)に対して、k色で頂点を塗り分ける時、距離が2以下の頂点に対して同じ色
を塗ってはいけないという制約下で、何通りの塗り分け方が存在するか。

解法：
ある頂点xに対して、その親が既に塗られている場合、xの子の数をcとして、xの子の塗り方の総数は
(k-2)Pc
なお、木の頂点の塗り方をk通りとした場合、それ以降は子の塗り方さえ考えれば良いので、x自体の塗り方の総数は
既に考慮されている。

また、根については、根と同時にその子について一気に決定する必要があり、
根の子の個数をcとして、kP(c+1)としなけらばならない。
"""
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
mod = 10**9+7


def factrial_memo(n=10**5+1,mod=10**9+7): 
    fact = [1, 1]  
    factinv = [1, 1]  
    inv = [0, 1]  
    for i in range(2, n + 1):
        fact.append((fact[-1] * i) % mod)
        inv.append((-inv[mod % i] * (mod // i)) % mod)
        factinv.append((factinv[-1] * inv[-1]) % mod)
    return fact,factinv 


fact,factinv = factrial_memo()

def permutation(n,m,mod=10**9+7): 
    return fact[n]*factinv[n-m]%mod

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

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


root = 0 
stack = [0]
parent = [0]*n
order = []
while stack:
    x = stack.pop()
    order.append(x)
    for i in g[x]:
        if i == parent[x]:
            continue
        parent[i] = x
        stack.append(i)

ans = 1

for x in order: 
    if len(g[x]) == 1 and x != root:
        continue
    if len(g[x]) >= k: 
        print(0)
        exit()
    if x == root:
        ans *= permutation(k,len(g[x])+1)
        ans %= mod
    else:
        ans *= permutation(k-2,len(g[x])-1)
        ans %= mod

print(ans)

Solution (Python):

"""
問題：
n頂点の木(辺の情報が与えられる)に対して、k色で頂点を塗り分ける時、距離が2以下の頂点に対して同じ色
を塗ってはいけないという制約下で、何通りの塗り分け方が存在するか。

解法：
ある頂点xに対して、その親が既に塗られている場合、xの子の数をcとして、xの子の塗り方の総数は
(k-2)Pc
なお、木の頂点の塗り方をk通りとした場合、それ以降は子の塗り方さえ考えれば良いので、x自体の塗り方の総数は
既に考慮されている。
"""
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
mod = 10**9+7


def factrial_memo(n=10**5+1,mod=10**9+7): 
    fact = [1, 1]  
    factinv = [1, 1]  
    inv = [0, 1]  
    for i in range(2, n + 1):
        fact.append((fact[-1] * i) % mod)
        inv.append((-inv[mod % i] * (mod // i)) % mod)
        factinv.append((factinv[-1] * inv[-1]) % mod)
    return fact,factinv 


fact,factinv = factrial_memo()

def permutation(n,m,mod=10**9+7): 
    return fact[n]*factinv[n-m]%mod

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

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


root = 0 
stack = [0]
parent = [0]*n
order = []
while stack:
    x = stack.pop()
    order.append(x)
    for i in g[x]:
        if i == parent[x]:
            continue
        parent[i] = x
        stack.append(i)

ans = 1

for x in order: 
    if len(g[x]) == 1 and x != root:
        continue
    if len(g[x]) >= k: 
        print(0)
        exit()
    if x == root:
        ans *= permutation(k,len(g[x])+1)
        ans %= mod
    else:
        ans *= permutation(k-2,len(g[x])-1)
        ans %= mod

print(ans)

Solution (Python):


MOD = 10 ** 9 + 7

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

    res = k
    stack = [0]
    visited = [False for i in range(n)]
    while stack:
        i = stack.pop()
        visited[i] = True
        children = [x for x in adj[i] if not visited[x]]
        res *= perm((k - 1 if i == 0 else k - 2), len(children))
        res %= MOD
        for c in children:
            stack.append(c)
    print(res)

def perm(t, s):
    res = 1
    for i in range(s):
        res *= t
        res %= MOD
        t -= 1
    return res

if __name__ == "__main__":
    main()

Solution (Python):


from functools import lru_cache

MOD = 10 ** 9 + 7

def main():
    n, k = map(int, input().split())
    adj = [[] for i in range(n)]
    for i in range(n - 1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        adj[a].append(b)
        adj[b].append(a)
    res = k
    stack = [0]
    visited = [False for i in range(n)]
    while stack:
        i = stack.pop()
        visited[i] = True
        children = [x for x in adj[i] if not visited[x]]
        res *= perm((k - 1 if i == 0 else k - 2), len(children))
        res %= MOD
        for c in children:
            stack.append(c)
    print(res)

@lru_cache(maxsize=10 ** 6)
def perm(t, s):
    if s > t:
        return 0
    res = 1
    for i in range(s):
        res *= t
        res %= MOD
        t -= 1
    return res

if __name__ == "__main__":
    main()

Solution (Python):


MOD = 10 ** 9 + 7

def main():
    n, k = map(int, input().split())
    adj = [[] for i in range(n)]
    for i in range(n - 1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        adj[a].append(b)
        adj[b].append(a)
    res = k
    stack = [0]
    visited = [False for i in range(n)]
    while stack:
        i = stack.pop()
        visited[i] = True
        children = [x for x in adj[i] if not visited[x]]
        res *= perm((k - 1 if i == 0 else k - 2), len(children))
        res %= MOD
        for c in children:
            stack.append(c)
    print(res)

def perm(t, s):
    if s > t:
        return 0
    res = 1
    for i in range(s):
        res *= t
        res %= MOD
        t -= 1
    return res

if __name__ == "__main__":
    main()

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

tree = [[] for _ 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)

not_yet = deque(tree[0])
already = [False]*n
already[0] = True
ans = k
key = k-1
for v in tree[0]:
  already[v] = True
  ans *= key
  ans %= inf
  key -= 1

while not_yet:
  key = not_yet.popleft()
  for v in range(k-2, k-1-len(tree[key]), -1):
    ans *= v
    ans %= inf
  
  for value in tree[key]:
    if already[value]:
      continue
    not_yet.append(value)
    already[value] = True

print(ans)

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

tree = [[] for _ 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)

not_yet = deque(tree[0])
already = [False]*n
already[0] = True
ans = k
key = k-1
for v in tree[0]:
  already[v] = True
  ans *= key
  ans %= inf
  key -= 1

while not_yet:
  key = not_yet.popleft()
  for v in range(k-2, k-1-len(tree[key]), -1):
    ans *= v
    ans %= inf
  
  for value in tree[key]:
    if already[value]:
      continue
    not_yet.append(value)
    already[value] = True

print(ans)

Solution (Python):
import sys

sys.setrecursionlimit(100000)
class Cmber:
    def __init__(self,gensize,mod=10**9+7):
        self.mod = mod
        self.g1=[1,1]
        self.g2 = [1, 1] 
        self.inverse = [0, 1] 
        self.getgen(gensize)
    def getgen(self,N):
        for i in range( 2, N + 1 ):
            self.g1.append( ( self.g1[-1] * i ) % self.mod )
            self.inverse.append( ( -self.inverse[self.mod % i] * (self.mod//i) ) % self.mod )
            self.g2.append( (self.g2[-1] * self.inverse[-1]) % self.mod )
    def per(self,n,r):
        if ( r<0 or r>n ):
            return 0

        return self.g1[n] * self.g2[n-r]  % self.mod        


    def cmb(self,n, r):
        if ( r<0 or r>n ):
            return 0
        r = min(r, n-r)
        return self.g1[n] * self.g2[r] * self.g2[n-r] % self.mod
 
    def cmb_very_high_n(self,n, r):
        if ( r<0 or r>n ):
            return 0
        g1=1
        r = min(r, n-r)
        for i in range(n-r+1,n+1):
            g1*=i
            g1%=self.mod
        return g1 * self.g2[r] % self.mod

    def multiple_cmb(self,vals):
        ans = self.g1[sum(vals)] % self.mod
        for i in vals:
            ans = (ans*self.g2[i])%self.mod
        return ans






def dfs(connections:list,node,oya,K,cmber:Cmber):

    if node == oya:
        children = connections[node]
        ans = cmber.per(K-1,len(children))

        for child in children:
            ans *= dfs(connections,child,node,K,cmber)
            ans %= cmber.mod

        return (ans * K) % cmber.mod

    if len(connections[node])==1:

        return 1


    children = [i for i in connections[node] if i != oya]

    ans = cmber.per(K-2,len(children))
    for child in children:
        ans *= dfs(connections,child,node,K,cmber)
        ans %= cmber.mod

    return ans





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

    cmber = Cmber(K)
    print(dfs(connections,0,0,K,cmber))







if __name__ == "__main__":
    resolve()

Solution (Python):
import sys
from collections import deque
MOD = 10 ** 9 + 7

n, k, *ab = map(int, sys.stdin.read().split())
graph = [[] for _ in range(n)]
for a, b in zip(*[iter(ab)] * 2):
  a -= 1; b -= 1
  graph[a].append(b)
  graph[b].append(a)

def main():
  for i in range(n):
    if len(graph[i]) + 1 > k:
      print(0)
      return
  
  cnt = [None] * n; cnt[0] = k
  parent = [None] * n
  stack = [0]
  while stack:
    u = stack.pop()
    c = k - 2 if not parent[u] is None else k - 1
    for v in graph[u]:
      if v == parent[u]: continue 
      parent[v] = u
      cnt[v] = c
      c -= 1
      stack.append(v)

  res = 1
  for c in cnt:
    res *= c
    res %= MOD
  print(res)

if __name__ == '__main__':
  main()

Solution (Python):
import sys
from collections import deque
MOD = 10 ** 9 + 7

n, k, *ab = map(int, sys.stdin.read().split())
graph = [[] for _ in range(n)]
for a, b in zip(*[iter(ab)] * 2):
  a -= 1; b -= 1
  graph[a].append(b)
  graph[b].append(a)

def main():
  for i in range(n):
    if len(graph[i]) + 1 > k:
      print(0)
      return
  
  cnt = [None] * n; cnt[0] = k
  parent = [None] * n
  stack = [0]
  while stack:
    u = stack.pop()
    c = k - 2 if not parent[u] is None else k - 1
    for v in graph[u]:
      if v == parent[u]: continue 
      parent[v] = u
      cnt[v] = c
      c -= 1
      stack.append(v)

  res = 1
  for c in cnt:
    res *= c
    res %= MOD
  print(res)

if __name__ == '__main__':
  main()

Solution (Python):
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, K = MAP()
L = [LIST() for i in range(N-1)]
color = [0] * N

graph = defaultdict(list)
for a, b in L:
    graph[a].append(b)
    graph[b].append(a)

ans = 1

q = deque([[1, 0, K]])



while q:
    u, p, k_ = q.popleft()
    ans = (ans * k_) % mod
    if p == 0:
        
        k_next = K - 1
    else:
        k_next = K - 2

    for v in graph[u]:
        if v == p:
            
            continue
        q.append([v, u, k_next])
        
        
        k_next -= 1
print(ans)

Solution (Python):


import sys

sys.setrecursionlimit(10**9)

def dfs(num):
    temp=K-len(way[num])
    
    for w in way[num]:
        if visited[w]==-1:
            visited[w]=temp
            temp+=1
            dfs(w)
    
    return 

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

mod=10**9+7

visited=[-1]*N
way=[[] for i in range(N)]

for _ in range(N-1):
    a,b=map(int,input().split())
    way[a-1].append(b-1)
    way[b-1].append(a-1)
    
color=[]
visited[0]=K
dfs(0)



ans=1
for item in visited:
    ans*=item
    ans%=mod
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
MOD = 10**9+7
N,K = map(int,input().split())
edge = [[] for _ in range(N)]
for i in range(N-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    edge[a].append(b)
    edge[b].append(a)

ans = 1
def dfs(now, par,num):
    global ans
    ans = ans*num%MOD
    num = K-1
    if par != -1:
        num -= 1
    for ch in edge[now]:
        if ch != par:
            dfs(ch,now,num)
            num -= 1

dfs(0,-1,K)
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
n, k = map(int, input().split())
edges = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = list(map(lambda x: int(x)-1, input().split()))
    edges[a].append(b)
    edges[b].append(a)
MOD = 10**9+7
INF = 10**10
dp = [INF]*n


def dfs(v, parent, x):
    dp[v] = x
    if parent == -1:
        next_x = k-1
    else:
        next_x = k-2
    for v2 in edges[v]:
        if v2 == parent:
            continue
        dfs(v2, v, next_x)
        next_x -= 1


dfs(0, -1, k)
ans = 1
for x in dp:
    ans = ans*x % MOD
print(ans)

Solution (Python):
N, K = map(int, input().split())
graph = [[] for i in range(N)]

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

stack = [0]
ans = K
mod = 10**9+7
r = [True] * N
r[0] = False
while stack:
    v = stack.pop()
    tmp = K - 1
    if v > 0:
        tmp -= 1
    for child in graph[v]:
        if r[child]:
            r[child] = False
            stack.append(child)
            ans *= tmp
            tmp -= 1
            ans %= mod
print(ans)

Solution (Python):
def main():
    from collections import deque
    from functools import reduce
    import sys
    input = sys.stdin.readline

    MOD = 10 ** 9 + 7

    def mod_mul(a, b):
        return a * b % MOD

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

    Graph = tuple(set() for _ in range(N))
    for _ in range(N - 1):
        a, b = (int(x) - 1 for x in input().split())
        Graph[a].add(b)
        Graph[b].add(a)

    dq = deque()
    color = [-1] * N
    color[0] = K
    used = 0
    for u in Graph[0]:
        color[u] = K - 1 - used
        used += 1
        dq.append(u)

    while dq:
        v = dq.popleft()
        used = 0
        for u in Graph[v]:
            if ~color[u]:
                continue
            color[u] = K - 2 - used
            used += 1
            dq.append(u)

    ans = reduce(mod_mul, color)

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):

MOD = 10**9 + 7
m = 10**5 + 5
fac = [0] * m
finv = [0] * m
inv = [0] * m


def COMBinitialize(m):
    fac[0] = 1
    finv[0] = 1
    if m > 1:
        fac[1] = 1
        finv[1] = 1
        inv[1] = 1
        for i in range(2, m):
            fac[i] = fac[i-1] * i % MOD
            inv[i] = MOD - inv[MOD % i] * (MOD // i) % MOD
            finv[i] = finv[i - 1] * inv[i] % MOD


COMBinitialize(m)


def main():
    N, K = (int(i) for i in input().split())
    edge = [[] for _ in range(N)]
    for i in range(N-1):
        a, b = (int(i) for i in input().split())
        edge[a-1].append(b-1)
        edge[b-1].append(a-1)
    acc = [1]*N
    from collections import deque

    def bfs(G, s):
        dist = [-1 for _ in range(N)]
        que = deque()
        dist[s] = 0
        c = len(edge[s]) - 1
        d = len(edge[s]) + 1
        if K < d:
            acc[s] = 0
            return
        acc[s] = fac[K] * finv[K - d]
        acc[s] %= MOD
        que.append(s)
        while que:
            u = que.popleft()
            c = len(edge[u]) - 1
            if K-2 < c:
                acc[u] = 0
                return
            if dist[u] >= 1 and c > 0:
                acc[u] = fac[(K-2)] * finv[(K-2) - c]
                acc[u] %= MOD
            for v in G[u]:
                if dist[v] != -1:
                    continue
                dist[v] = dist[u] + 1
                que.append(v)

    bfs(edge, 0)
    ans = 1
    for a in acc:
        ans *= a
        ans %= MOD
    print(ans % MOD)


if __name__ == '__main__':
    main()

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
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,k = inpl()
g = [[] for _ in range(n)]
for i in range(n-1):
    a,b = inpl()
    a -= 1; b -= 1
    g[a].append(b)
    g[b].append(a)
res = k
q = deque()
q.append(0)
fin = set()
fin.add(0)
while q:
    v = q.popleft()
    cnt = 1 if v == 0 else 2
    for nv in g[v]:
        if nv in fin:
            continue
        res *= k-cnt
        res %= mod
        cnt += 1
        fin.add(nv)
        q.append(nv)
print(res)

Solution (Python):
def main():
    import collections
    N, K = map(int, input().split())
    G = [set() for i in range(N)]

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

    q = collections.deque()
    q.append((0))
    ans = K
    mod = 10**9+7
    r = [True]*N
    r[0] = False
    while(q):
        x = q.popleft()
        tmp = K - 1
        if x > 0:
            tmp -= 1
        for y in G[x]:
            if r[y]:
                r[y] = False
                q.append(y)
                ans *= tmp
                tmp -= 1
                ans %= mod
    print(ans)


main()

Solution (Python):
import fractions
import collections
N, K = map(int, input().split())
G = [set() for i in range(N)]

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

q = collections.deque()
q.append((0))
ans = K
mod = 10**9+7
r = [True]*N
r[0] = False
while(q):
    x = q.popleft()
    tmp = K - 1
    if x > 0:
        tmp -= 1
    for y in G[x]:
        if r[y]:
            r[y] = False
            q.append(y)
            ans *= tmp
            tmp -= 1
            ans %= mod
print(ans)

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

class Combination:
    def __init__(self, size, mod=10**9 + 7):
        self.size = size + 2
        self.mod = mod
        self.fact = [1, 1] + [0] * size
        self.factInv = [1, 1] + [0] * size
        self.inv = [0, 1] + [0] * size

        for i in range(2, self.size):
            self.fact[i] = self.fact[i - 1] * i % self.mod
            self.inv[i] = -self.inv[self.mod % i] * (self.mod // i) % self.mod
            self.factInv[i] = self.factInv[i - 1] * self.inv[i] % self.mod

    def npr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * self.factInv[n - r] % self.mod

    def ncr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * (self.factInv[r] * self.factInv[n - r] % self.mod) % self.mod

    def nhr(self, n, r):  
        return self.ncr(n + r - 1, n - 1)

    def factN(self, n):
        if n < 0:
            return 0
        return self.fact[n]

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

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

def dfs(now, pr):
    ret = 1

    cnt = 0
    for to in edges[now]:
        if to == pr:
            continue
        cnt += 1
        ret = (ret * dfs(to, now)) % MOD

    color = K - 1 if pr == -1 else K - 2
    ret = (ret * comb.npr(color, cnt)) % MOD

    return ret

print(dfs(0, -1) * K % MOD)

Solution (Python):
mod = 10**9+7
n,k = map(int,input().split())
ki = [[]for _ in range(n)]
l = max(n,k)
frac = [1]*(l+1)
for i in range(1,l+1):
    frac[i] = (frac[i-1]*i)%mod
invfrac = [1] *(l+1)
invfrac[-1] = pow(frac[-1],mod-2,mod)
for i in range(l-1,0,-1):
    invfrac[i] = (invfrac[i+1]*(i+1))%mod

def P(x,y):
    return (frac[x]*invfrac[x-y])%mod
    

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

stack = [0]
visited = [0]*n
visited[0] = 1
ans = 1
while stack:
    next = []
    for now in stack:
        visited[now] = 1
        
        if now !=0:
            ans *=P(k-2,len(ki[now])-1)
            if len(ki[now])-1 >= k-1:ans = 0
            
            ans %=mod
        for x in ki[now]:
            if visited[x]:continue
            next.append(x)
    stack = next
ans *= P(k,len(ki[0])+1)
ans %=mod
print(ans)

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

DIV=10**9+7

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

E=[[] for i in range(N)]

for i in range(N-1):
  a,b=map(int,readline().split())
  E[a-1].append(b-1)
  E[b-1].append(a-1)
  
ans=1
stack=[]

stack.append([0,-1,0,0])
while stack:
  v,parent,minus,base=stack.pop()
  ans = (ans%DIV * (K-(minus+base))%DIV) % DIV
  if base < 2:
    base += 1
  cnt=0
  for child in E[v]:
    if child == parent:
      continue
    stack.append([child,v,cnt,base])
    cnt+=1
  
print(ans)

Solution (Python):
from collections import deque

def P(n, r):
    if ( r<0 or r>n ):
        return 0
    return g1[n] * g2[n-r] % mod

mod = 10**9+7 
N = 10**5+30
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=map(int,input().split())
G=[[] for i in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  a=a-1
  b=b-1
  G[a].append(b)
  G[b].append(a)
D=deque([0])
DD=[0]
V=[0]*n
V[0]=1
GG=[[] for i in range(n)]
while len(D)>0:
  x=D[0]
  D.popleft()
  for i in range(len(G[x])):
    if V[G[x][i]]==0:
      V[G[x][i]]=1
      GG[x].append(G[x][i]) 
      D.append(G[x][i])
      DD.append(G[x][i])
ans=k*P(k-1,len(GG[0]))%mod  
for i in range(1,n):  
  if len(GG[i])==0:
    continue
  ans=ans*P(k-2,len(GG[i]))%mod
print(ans)

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

N,K = map(int,input().split())
T = [[]*N for i in range(N)]
for i in range(N-1):
    a,b = map(int,input().split())
    T[a-1].append(b-1)
    T[b-1].append(a-1)
visited = [0]*N
ans = 1
def bfs(i,bb,b):
    global ans
    visited[i] = 1
    ans = (ans*(K-bb-b))%(10**9+7)
    cnt = 0
    for j in T[i]:
        if visited[j] == 1:
            continue
        bfs(j,b+cnt,1)
        cnt += 1
bfs(0,0,0)
print(ans)

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

N,K = map(int,input().split())
E = [[] for _ in range(N)]
MOD = 10**9+7

for _ in range(N-1):
	u,v = map(int,input().split())
	u -= 1
	v -= 1
	E[u].append(v)
	E[v].append(u)

color = [-1 for _ in range(N)]

stack = []
color[0] = 1
ans = K
for i,v in enumerate(E[0]):
	stack.append(v)
	ans *= (K-i-1)
	ans %= MOD

while stack:
	u = stack.pop()
	color[u] = 1
	length = 0
	for v in E[u]:
		if color[v] == -1:
			stack.append(v)
			length += 1
	tmp = 1
	for i in range(K-1-length,K-1):
		tmp *= i
		tmp %= MOD
	ans *= tmp
	ans %= MOD

print(ans%MOD)

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

N,K = map(int,input().split())
E = [[] for _ in range(N)]
MOD = 10**9+7

for _ in range(N-1):
	u,v = map(int,input().split())
	u -= 1
	v -= 1
	E[u].append(v)
	E[v].append(u)

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

color = [-1 for _ in range(N)]

stack = []
color[u] = 1
ans = K
for i,v in enumerate(E[u]):
	stack.append(v)
	ans *= (K-i-1)
	ans %= MOD

while stack:
	u = stack.pop()
	color[u] = 1
	length = 0
	for v in E[u]:
		if color[v] == -1:
			stack.append(v)
			length += 1
	tmp = 1
	for i in range(K-1-length,K-1):
		tmp *= i
		tmp %= MOD
	ans *= tmp
	ans %= MOD

print(ans%MOD)

Solution (Python):
import sys
input = sys.stdin.readline
N,K = map(int,input().split())
E = [[] for _ in range(N)]
MOD = 10**9+7

for _ in range(N-1):
	u,v = map(int,input().split())
	u -= 1
	v -= 1
	E[u].append(v)
	E[v].append(u)

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

color = [-1 for _ in range(N)]
dp = [-1 for _ in range(N)]

stack = []
color[u] = 1
ans = K
for i,v in enumerate(E[u]):
	stack.append(v)
	ans *= (K-i-1)
	ans %= MOD

while stack:
	u = stack.pop()
	color[u] = 1
	length = 0
	for v in E[u]:
		if color[v] == -1:
			stack.append(v)
			length += 1
	if dp[length] == -1:
		tmp = 1
		for i in range(K-1-length,K-1):
			tmp *= i
			tmp %= MOD
		ans *= tmp
		dp[length] = tmp
	else:
		ans *= dp[length]
	ans %= MOD

print(ans%MOD)

Solution (Python):
import sys

N,K = map(int,input().split())
E = [[] for _ in range(N)]
MOD = 10**9+7

for _ in range(N-1):
	u,v = map(int,input().split())
	u -= 1
	v -= 1
	E[u].append(v)
	E[v].append(u)

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

color = [-1 for _ in range(N)]
dp = [-1 for _ in range(N)]

stack = []
color[u] = 1
ans = K
for i,v in enumerate(E[u]):
	stack.append(v)
	ans *= (K-i-1)
	ans %= MOD

while stack:
	u = stack.pop()
	color[u] = 1
	length = 0
	for v in E[u]:
		if color[v] == -1:
			stack.append(v)
			length += 1
	if dp[length] == -1:
		tmp = 1
		for i in range(K-1-length,K-1):
			tmp *= i
			tmp %= MOD
		ans *= tmp
		dp[length] = tmp
	else:
		ans *= dp[length]
	ans %= MOD

print(ans%MOD)