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

    """ convenient functions
    
    
    
    
    
    """

    """convenient decorator
    
    
        
        
        
        
        
        
        
        
        
        
    """
    
    
    import sys
    sys.setrecursionlimit(10**7)
    from itertools import accumulate, combinations, permutations, product 
    
    from math import factorial, ceil, floor, sqrt
    def factorize(n):
        """return the factors of the Arg and count of each factor
        
        Args:
            n (long): number to be resolved into factors
        
        Returns:
            list of tuples: factorize(220) returns [(2, 2), (5, 1), (11, 1)]
        """
        fct = []  
        b, e = 2, 0  
        while b * b <= n:
            while n % b == 0:
                n = n // b
                e = e + 1
            if e > 0:
                fct.append((b, e))
            b, e = b + 1, 0
        if n > 1:
            fct.append((n, 1))
        return fct
    def combinations_count(n, r):
        """Return the number of selecting r pieces of items from n kinds of items.
        
        Args:
            n (long): number
            r (long): number
        
        Raises:
            Exception: not defined when n or r is negative
        
        Returns:
            long: number
        """
        
        if n < 0 or r < 0:
            raise Exception('combinations_count(n, r) not defined when n or r is negative')
        if n - r < r: r = n - r
        if r < 0: return 0
        if r == 0: return 1
        if r == 1: return n
        numerator = [n - r + k + 1 for k in range(r)]
        denominator = [k + 1 for k in range(r)]
        for p in range(2,r+1):
            pivot = denominator[p - 1]
            if pivot > 1:
                offset = (n - r) % p
                for k in range(p-1,r,p):
                    numerator[k - offset] /= pivot
                    denominator[k] /= pivot
        result = 1
        for k in range(r):
            if numerator[k] > 1:
                result *= int(numerator[k])
        return result
    def combinations_with_replacement_count(n, r):
        """Return the number of selecting r pieces of items from n kinds of items allowing individual elements to be repeated more than once.
        
        Args:
            n (long): number
            r (long): number
        
        Raises:
            Exception: not defined when n or r is negative
        
        Returns:
            long: number
        """
        if n < 0 or r < 0:
            raise Exception('combinations_with_replacement_count(n, r) not defined when n or r is negative')
        elif n == 0:
            return 1
        else:
            return combinations_count(n + r - 1, r)
    from bisect import bisect_left, bisect_right
    from collections import deque, Counter, defaultdict 
    from heapq import heapify, heappop, heappush, heappushpop, heapreplace,nlargest,nsmallest 
    from copy import deepcopy, copy 
    import operator
    from operator import itemgetter
    
    
    from functools import reduce, lru_cache
    def chmin(x, y):
        """change minimum
        if x > y, x = y and return (x, True).
        convenient when solving problems of dp[i]
        
        Args:
            x (long): current minimum value
            y (long): potential minimum value
        
        Returns:
            (x, bool): (x, True) when updated, else (x, False)
        """
        if x > y:
            x = y
            return (x, True)
        else:
            return (x, False)
    def chmax(x, y):
        """change maximum
        if x < y, x = y and return (x, True).
        convenient when solving problems of dp[i]
        
        Args:
            x (long): current maximum value
            y (long): potential maximum value
        
        Returns:
            (x, bool): (x, True) when updated, else (x, False)
        """
        if x < y:
            x = y
            return (x, True)
        else:
            return (x, False)

    from fractions import gcd 
    def gcds(numbers):
        return reduce(gcd, numbers)
    def lcm(x, y):
        return (x * y) // gcd(x, y)
    def lcms(numbers):
        return reduce(lcm, numbers, 1)

    
    
    INF = 10 ** 18
    MOD = 10 ** 9 + 7
    modpow = lambda a, n, p = MOD: pow(a, n, p) 
    def modinv(a, p = MOD):
        
        
        return modpow(a, p-2, p)
    def modinv_list(n, p = MOD):
        if n <= 1:
            return [0,1][:n+1]
        else:
            inv_t = [0,1]
            for i in range(2, n+1):
                inv_t += [inv_t[p % i] * (p - int(p / i)) % p]
            return inv_t
    def modfactorial_list(n, p = MOD):
        if n == 0:
            return [1]
        else:
            l = [0] * (n+1)
            tmp = 1
            for i in range(1, n+1):
                tmp = tmp * i % p
                l[i] = tmp
            return l
    def modcomb(n, k, fac_list = [], p = MOD):
        
        
        from math import factorial
        if n < 0 or k < 0 or n < k: return 0
        if n == 0 or k == 0: return 1
        if len(fac_list) <= n:
            a = factorial(n) % p
            b = factorial(k) % p
            c = factorial(n-k) % p
        else:
            a = fac_list[n]
            b = fac_list[k]
            c = fac_list[n-k]
        return (a * modpow(b, p-2, p) * modpow(c, p-2, p)) % p
    def modadd(a, b, p = MOD):
        return (a + b) % MOD
    def modsub(a, b, p = MOD):
        return (a - b) % p
    def modmul(a, b, p = MOD):
        return ((a % p) * (b % p)) % p
    def moddiv(a, b, p = MOD):
        return modmul(a, modpow(b, p-2, p))

    """ initialize variables and set inputs
    
        
        
    
        
        
        
        
        
    
        
        
        
        
    
        
        
    """

    
    r = lambda: sys.stdin.readline().strip()
    r_int = lambda: int(r())
    R = lambda: list(map(int, r().split()))
    Rmap = lambda: map(int, r().split())
    Rfloat = lambda: list(map(float, r().split()))
    Rtuple = lambda: tuple(map(int, r().split()))

    """ how to treat input
    
    
    
    
    
    
    
    """

    if __name__ != '__main__':
        
        sys.stdin = open('sample.txt')

    
    
    
    N, K = R()
    AB = [R() for _ in range(N-1)]
    
    task = deque()
    arrived = [0] * N
    tree = [set() for i in range(N)]
    for a, b in AB:
        a -= 1
        b -= 1
        tree[a].add(b)
        tree[b].add(a)

    arrived2 = [0] * N
    for i in tree[0]:
        task.append(i)
    
    task.append(-1) 
    arrived2[0] = 1
    ans = K
    tmp = K - 1
    while task:
        i = task.popleft()
        if i == -1:
            tmp = K - 2
        else:
            if arrived2[i] == 1:
                continue
            else:
                ans *= tmp
                ans %= MOD
                arrived2[i] = 1
                tmp -= 1
                for j in tree[i]:
                    if arrived2[j] == 0:
                        task.append(j)
                task.append(-1)
    
    print(ans)

    

    
    
    
    
    
    

    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    

    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    

    
    
    
        
    
    
    
    

    """memo: how to use defaultdict of list
    
    Dic = defaultdict(list)
    
    Dic[x].append(y)
    
    for k, v in Dic.items():
    """

if __name__ == '__main__':
    main()

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

def dfs(u, p, c):
    l = len([i for i in V[u] if i != p])
    n = K - 2
    if p == 0:
        n += 1
    if l == 0:
        return c
    for v in V[u]:
        if v == p:
            continue
        c *= dfs(v, u, n)
        n -= 1
        c %= MOD
    return c

print(dfs(1, 0, K))

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)

mod = 10 ** 9 + 7

input = sys.stdin.readline


def rec(v, bf):
    global ans
    gs[v] += 1
    gs[bf] += 1
    ans = ans * (K - gs[bf]) % mod
    for nv in es[v]:
        if nv == bf: continue
        rec(nv, v)
    return


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

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

gs = [0] * (N + 1)
gs[0] = -1
gs[N] = -1

ans = 1

rec(0, N)
print(ans)

Solution (Python):
N,K=map(int,input().split())
ab=[list(map(int,input().split())) for _ in range(N-1)]
graph=[[] for _ in [0]*N]
[graph[a-1].append(b-1) for a,b in ab]
[graph[b-1].append(a-1) for a,b in ab]
q=[[-1,0]]
cnt=0
ans=K
mod=10**9+7
while(q):
    q1=[]
    if cnt<2:
        cnt+=1
    for i,j in q:
        g=graph[j]
        if i!=-1:
            g.remove(i)
        for cnt2,k in enumerate(g):
            q1.append([j,k])
            ans=(ans*(K-cnt-cnt2))%mod
    q=q1
print(ans)

Solution (Python):
from collections import deque
N, K = map(int, input().split())
edges = [list(map(int, input().split())) for _ in range(N - 1)]
MOD = 10 ** 9 + 7

def dfs(u, par):
    q = deque()
    q.append((u, par))
    ret = 1

    while q:
        u, par = q.pop()
        color_num = K - 1 if par == -1 else K - 2
        
        if len(graph[u]) > K:
            return 0
            
        for v in graph[u]:
            if v == par:
                continue
                
            ret *= color_num
            ret %= MOD
            color_num -= 1
            
            q.append((v, u))

    return ret

graph = [[] for _ in range(N)]
for u, v in edges:
    graph[u - 1].append(v - 1)
    graph[v - 1].append(u - 1)

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

Solution (Python):


import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline 
MOD = 10**9+7


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

ans = 1
ok = [k]*n

def dfs(v,p): 

    global ans
    ans *= ok[p]
    ans %= MOD
    if p!=v: ok[p] -= 1
    ok[v] -= 1
    for c in g[v]:
        if c == p: continue
        ok[c] -= 1
        dfs(c,v)

dfs(0,0)

print(ans)

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

def main():
	N, K = map(int, input().split())
	DIV = 10**9+7
	ab = [[] for _ in range(N)]

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

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

	def dfs(v, p=-1):
		c = 0
		ans = 1
		for u in ab[v]:
			if u == p:
				continue
			c += 1
			ans = ans * dfs(u, v) % DIV
		nk = K-1
		if p != -1:
			nk = K-2
		ans *= P(nk, c)
		return ans%DIV
	ans = dfs(0)*K%DIV
	print(ans)


if __name__ == '__main__':
	main()

Solution (Python):
mo=10**9+7
n,k=map(int,input().split())

def P(n,k,mo):
    rt=1
    for i in range(k):
        rt*=(n-i)
        rt%=mo
    return rt

g=[[] for i in range(1+n)]
v=[0]*(1+n)

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

def dfs(cur):
    q=[]
    q.append(cur)

    while q:
        cur=q.pop()
        v[cur]=1
        c=len(g[cur])-1
        ans[0]*=P(k-2,c,mo)
        
        for nb in g[cur]:
            if v[nb]!=1:
                q.append(nb)
v[1]=1
ans=[P(k,1+len(g[1]),mo)]

for j in g[1]:
    dfs(j)
print(ans[0]%mo)

Solution (Python):
from math import factorial as f
from sys import exit

def main():
    bign = 10**9+7
    n,k = map(int,input().split())

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

    if len(edge[1]) > k-1:
        print(0)
        exit()
    ans = (f(k)//f(k-1-len(edge[1])))%bign

    for i in range(2,n+1):
        if len(edge[i]) > k-1:
            print(0)
            exit()
        if len(edge[i])==1:
            continue
        t = k-2
        for j in range(len(edge[i])-1):
            ans = ans * t % bign
            t-=1
        
    print(ans)


main()

Solution (Python):
import sys
mod = 1000000007

sys.setrecursionlimit(10**7)
readline = sys.stdin.readline
N, K = map(int, readline().split())

def P(x, y):
    r = 1
    for i in range(y):
        r = (r * (x - i)) % mod
    return r

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

def dfs(bb, v):
    cn = 0
    r = 1
    for u in G[v]:
        if u == bb:
            continue
        cn += 1
        r = (r * dfs(v, u)) % mod
    if cn == 0:
        return 1
    else:
        if bb == None:
            return P(K-1, cn) * r % mod
        else:
            return P(K-2, cn) * r % mod

print((K*dfs(None, 0))%mod)

Solution (Python):
import sys
sys.setrecursionlimit(100000)
x=10**9+7
n,k=map(int,input().split())
t=[set()for _ in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  t[a-1].add(b);t[b-1].add(a)
c=k
def b(o):
  global c
  for i,j in enumerate(t[o-1]):c=(c*(k-2-i))%x;t[j-1].discard(o);b(j)
for i,j in enumerate(t[0]):c=(c*(k-1-i))%x;t[j-1].discard(1);b(j)
print(c)

Solution (Python):
def e_virus_tree_2(N, K, Edges, MOD=10**9 + 7):
    
    import sys
    sys.setrecursionlimit(10**6)

    class Permutation(object):
        
        __slots__ = ["mod", "factorial", "inverse"]

        def __init__(self, max_n: int = 10**6, mod: int = 10**9 + 7):
            fac, inv = [1], []
            fac_append, inv_append = fac.append, inv.append

            for i in range(1, max_n + 1):
                fac_append(fac[-1] * i % mod)

            inv_append(pow(fac[-1], mod - 2, mod))

            for i in range(max_n, 0, -1):
                inv_append(inv[-1] * i % mod)

            self.mod, self.factorial, self.inverse = mod, fac, inv[::-1]

        def permutation(self, n, r):
            if r < 0 or n < r:
                return 0
            return self.factorial[n] * self.inverse[n - r] % self.mod

    tree = [[] for _ in range(N)]
    for a, b in Edges:
        tree[b - 1].append(a - 1)
        tree[a - 1].append(b - 1)
    perm = Permutation(K).permutation

    def dfs(current, parent):
        
        
        
        
        ret = (perm(K, len(tree[current]) + 1) if parent == -1
               else perm(K - 2, len(tree[current]) - 1))

        for child in tree[current]:
            if child == parent:
                continue
            ret *= dfs(child, current)
            ret %= MOD
        return ret
    return dfs(0, -1)

N, K = [int(i) for i in input().split()]
Edges = [[int(i) for i in input().split()] for j in range(N - 1)]
print(e_virus_tree_2(N, K, Edges))

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

MOD = 1000000007

def dfs(par, v):
    val = nColors - 1 if par == 0 else nColors - 2
    for child in edges[v]:
        if child != par:
            ways[child] = max(0, val)
            val -= 1
            dfs(v, child)

nVertices, nColors = map(int, input().split())
edges = [[] for _ in range(nVertices + 1)]
for _ in range(nVertices - 1):
    u, v = map(int, input().split())
    edges[u].append(v)
    edges[v].append(u)

ways = [0] * (nVertices + 1)
ways[1] = nColors
dfs(0, 1)
ret = 1
for w in ways[1:]:
    ret = (ret * w) % MOD
print(ret)

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

MOD = 1000000007

def dfs(par, v, val):
    for child in edges[v]:
        if child != par:
            ways[child] = max(0, val)
            val -= 1
            dfs(v, child, nColors - 2)

nVertices, nColors = map(int, input().split())
edges = [[] for _ in range(nVertices + 1)]
for _ in range(nVertices - 1):
    u, v = map(int, input().split())
    edges[u].append(v)
    edges[v].append(u)

ways = [0] * (nVertices + 1)
ways[1] = nColors
dfs(0, 1, nColors - 1)
ret = 1
for w in ways[1:]:
    ret = (ret * w) % MOD
print(ret)

Solution (Python):
MOD = 1000000007
N, K = map(int,input().split())
G = [[] 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)

C = [False for _ in range(N)]
F = [0]
C[0] = True
r = K
while F:
    n = F.pop()
    if n == 0:
        c = K-1
    else:
        c = K-2
    for e in G[n]:
        if C[e]:
            continue
        C[e] = True
        r = (r * c) % MOD
        c -= 1
        F.append(e)

print(r)

Solution (Python):
import sys
import collections as col
import numpy as np
MOD = 1000000007


def input():
    return sys.stdin.readline().rstrip()


def main():
    n, k = [int(e) for e in input().split()]
    adj = [[] for _ in range(n+1)]
    for _ in range(n-1):
        u, v = [int(e) for e in input().split()]
        adj[u].append(v)
        adj[v].append(u)

    ans = 1
    queue = col.deque([(1, 0, k)])
    while len(queue) > 0:
        u, p, k_ = queue.popleft()
        ans = (ans * k_) % MOD
        if p == 0:
            k_next = k - 1
        else:
            k_next = k - 2
        for v in adj[u]:
            if v == p:
                continue
            queue.append((v, u, k_next))
            k_next -= 1
    print(ans)


main()

Solution (Python):
from collections import deque
import math
import sys
mod = 10**9+7
N,K = map(int,input().split())


Kperm =[1,K]
pre = K
for i in range(2,K+1):
    pre = (pre*(K+1-i))%mod
    Kperm.append(pre)



K_2perm =[1,K-2]
pres = K-2
for i in range(2,K-1):
    pres = (pres*(K-1-i))%mod
    K_2perm.append(pres)

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

if len(child[0])>=K:
    print(0);sys.exit()
ans = Kperm[len(child[0])+1]

went = [False] * N
queue = deque()
queue.append(0)
went[0] = True
while queue:
    cur = queue.pop()
    if cur!=0 and len(child[cur])>=K:
        print(0)
        sys.exit()
    if cur!=0:
        ans *= K_2perm[len(child[cur])-1]
        ans %= mod
    for togo in child[cur]:
        if not went[togo]:
            went[togo] = True
            queue.append(togo)
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(int, input().split())
  E[a-1].append(b-1)
  E[b-1].append(a-1)
counts = [False]*N
q = [0]
counts[0] = True
r = K
while q:
  i = q.pop()
  
  js = E[i]
  c = K-1 if i == 0 else K-2
  for j in js:
    if counts[j]:
      continue
    counts[j] = True
    r = (r*c)%1000000007
    c -= 1
    q.append(j)
print(r)

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)
counts = [False]*N
q = [0]
counts[0] = True
r = K
while q:
  i = q.pop(0)
  
  js = E[i]
  c = K-1 if i == 0 else K-2
  for j in js:
    if not(counts[j]):
      counts[j] = True
      r = (r*c)%1000000007
      c -= 1
      q.append(j)
print(r)

Solution (Python):
n,k=map(int,input().split())
mod=10**9+7
import sys
sys.setrecursionlimit(10**9)
root=[[] for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    root[a-1].append(b-1)
    root[b-1].append(a-1)
def perm(k,n):
    x=1
    if k-n+1<=0:
        return 0
    for i in range(k,k-n,-1):
        x=x*i%mod
    return x
def dfs(node,depth,prev): 
    l=len(root[node])
    d=depth
    x=1
    if l==0:
        return 1
    if l==1 and depth>1:
        return 1
    if depth>1:
        x=perm(k-d,l-1)
    else:
        x=perm(k-d,l)
    for y in root[node]:
        if y!=prev:
            x=x*dfs(y,2,node)%mod
    return x%mod
count=dfs(0,1,0)*k%mod
print(count if count>0 else 0)

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)
counts = [False]*N
q = [0]
counts[0] = True
r = K
while len(q) > 0:
  i = q.pop(0)
  
  js = E[i]
  c = K-1 if i == 0 else K-2
  for j in js:
    if not(counts[j]):
      counts[j] = True
      r = (r*c)%1000000007
      c -= 1
      q.append(j)
print(r)

Solution (Python):

import copy
import random
import bisect 
import fractions 
import math
import sys

mod = 10**9+7
sys.setrecursionlimit(mod) 

def LI(): return list(map(int, sys.stdin.readline().split()))


N,K = LI()
ab = [0 for i in range(N-1)]
for i in range(N-1):
    ab[i] = LI()

edges = {}
for i in range(N):
    edges[i] = []
count = [0 for i in range(N)]
for i in range(N-1):
    a,b = ab[i]
    a -= 1
    b -= 1
    edges[a].append(b)
    edges[b].append(a)

def dfs(node,p):
    cnt = 0
    for i,new_node in enumerate(edges[node]):
        if new_node == p:
            continue
        else:
            p_cnt = 2
            if node == 0:
                p_cnt = 1
            count[new_node] = K - p_cnt - cnt
            cnt += 1
            dfs(new_node,node)


count[0] = K
dfs(0,-1)

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

print(ans)

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

N,K = map(int,input().split())
edge = [[] for i in range(N)]
for i in range(N-1) :
    u,v = map(lambda x: int(x)-1, input().split())
    edge[u].append(v)
    edge[v].append(u)

deg = [len(E) for E in edge]

MOD = 10**9 + 7
u = 10**5 + 1

fact = [1] * (u+1)
for i in range(1, len(fact)) :
    fact[i] = (fact[i-1] * i) % MOD

fact_inv = [1] * (u+1)
fact_inv[u] = pow(fact[u], MOD-2, MOD)
for i in range(u-1,0,-1) :
    fact_inv[i] = (fact_inv[i+1] * (i+1)) % MOD

def perm(n, r) :
    if r < 0 or n < r :
        return 0
    return (fact[n] * fact_inv[n-r]) % MOD

def F(node, parent=None) :
    if parent is None :
        res = perm(K, deg[node] + 1)
    else :
        res = perm(K-2, deg[node] - 1)
    
    for next_node in edge[node] :
        if next_node == parent :
            continue
        
        res *= F(next_node, parent=node)
        res %= MOD
    return res

ans = F(0, parent=None)

print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(100005)
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)


mod = 10**9+7
def dfs(cur, pre):
    ret = 1
    nodecnt = 0 if pre == -1 else 1
    if cur > n-1 or cur < 0: return 0
    for nd in Tree[cur]:
        
        if nd == pre: continue
        nodecnt += 1
        ret = ret*(k-nodecnt)%mod
        ret = ret*dfs(nd, cur)%mod
    return ret%mod

print(k*dfs(0,-1)%mod)

Solution (Python):
from collections import defaultdict
import sys

sys.setrecursionlimit(10 ** 6)

def per(a, b):
    t = (a, b)
    if t in memo:
        return memo[t]
    re = 1
    for i in range(b):
        re = re * (a - i) % md
    memo[t] = re
    return re

def dfs(i, oi):
    cnt_ko = len(to[i])
    if i == 1:
        re = k * per(k - 1, cnt_ko) % md
    elif cnt_ko == 1:
        return 1
    else:
        re = per(k - 2, cnt_ko - 1)
    for ki in to[i]:
        if ki == oi: continue
        re = re * dfs(ki, i) % md
    return re

md = 10 ** 9 + 7
memo = {}
n, k = map(int, input().split())
to = defaultdict(list)
for _ in range(n - 1):
    a, b = map(int, input().split())
    to[a] += [b]
    to[b] += [a]
print(dfs(1, 0))

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

MOD = 10 ** 9 + 7

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

L = [[] for _ in range(n)]

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

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

def func(s, p):
    if len(L[s]) == 1:
        return 1
    ret = perm(k-2, len(L[s])-1)
    for x in L[s]:
        if x == p:
            continue
        ret = (ret * func(x, s)) % MOD
    return ret

ans = perm(k, len(L[0]) + 1)


for x in L[0]:
    ans = (ans * func(x, 0)) % MOD

print(ans)

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

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

dq = deque([0])
ans = K
check = [True]*N
check[0] = False
while dq:
    p = dq.popleft()
    if p == 0:
        cand = K-1
    else:
        cand = K-2
    for i in A[p]:
        if check[i]:
            check[i] = False
            ans = (ans*cand)%MOD
            cand -= 1
            dq.append(i)

print(ans)

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

N,K = map(int,input().split())
edge = [[] for i in range(N)] 
for i in range(N-1) :
    u,v = map(lambda x: int(x)-1, input().split())
    edge[u].append(v)
    edge[v].append(u)

deg = [len(E) for E in edge] 

MOD = 10**9 + 7
u = 10**5 + 1

fact = [1]*(u+1)
for i in range(1, len(fact)) :
    fact[i] = (fact[i-1] * i) % MOD

fact_inv = [1]*(u+1)
fact_inv[u] = pow(fact[u], MOD-2, MOD)
for i in range(u-1,0,-1) :
    fact_inv[i] = (fact_inv[i+1] * (i+1)) % MOD

def perm(n, k) : 
    if k < 0 or n < k :
        return 0
    return (fact[n] * fact_inv[n-k]) % MOD

def F(node, parent=None) :
    if parent is None :
        res = perm(K, deg[node] + 1) 
    else :
        res = perm(K-2, deg[node] - 1) 
    
    for next_node in edge[node] :
        if next_node == parent :
            continue
        res *= F(next_node, parent=node)
        res %= MOD
    return res

ans = F(0, parent=None)

print(ans)

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

def bfs(_N,_Nei,_K):
    mod = 10**9 + 7
    Q = []
    memo = [-1]*(_N+1)
    memo[1] = 0
    next = 1
    temp = len(_Nei[1])
    ans = _K
    for k in range(1,temp+1):
        ans = (ans*(_K-k))%mod
    for node in Nei[1]:
        memo[node] = 1
        Q.append(node)
    
    while True:
        temp = _K - 2
        for node in Nei[next]:
            if memo[node] == -1:
                Q.append(node)
                memo[node] = memo[next] + 1
                ans = (ans*temp)%mod
                temp -= 1

        if len(Q) == 0:
            return ans
        else:
            next = Q.pop(0)
print(bfs(N,Nei,K))

Solution (Python):
Q = 10**9+7


from collections import deque
def main():
    N, K = map( int, input().split())
    E = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b = map( lambda x: x-1, map( int, input().split()))
        E[a].append(b)
        E[b].append(a)
    V = [0]*N
    V[0] = K
    d = deque()
    for i in range( len(E[0])):
        t = E[0][i]
        V[t] = K - 1 - i
        if K == i+1:
            print(0)
            return
        cnt = 0
        for v in E[t]:
            if V[v] == 0:
                d.append(v)
                if K == cnt+2:
                    print(0)
                    return
                V[v] = K-2-cnt
                cnt += 1
    while d:
        t = d.popleft()
        cnt = 0
        for v in E[t]:
            if V[v] == 0:
                d.append(v)
                if K == cnt+2:
                    print(0)
                    return
                V[v] = K-2-cnt
                cnt += 1
    ans = 1
    for v in V:
        ans *= v
        ans %= Q
    print(ans)
    
if __name__ == '__main__':
    main()

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
from functools import reduce
import sys
import math
import bisect
import random
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return list(map(float, sys.stdin.readline().split()))
def LS():return sys.stdin.readline().split()
def SR(n): return [list(sys.stdin.readline())[:-1] for i in range(n)]
def IR(n): return [int(sys.stdin.readline()) for i in range(n)]
def LIR(n): return [list(map(int, sys.stdin.readline().split())) for i in range(n)]
def LSR(n): return [list(map(list, sys.stdin.readline().split())) for i in range(n)]
_gcd = lambda x, y: _gcd(y, x%y) if (x%y) else y
_lcm = lambda x, y: x*y // _gcd(x, y)
def gcd(*numbers):
    return reduce(_gcd, numbers)
def lcm(*numbers):
    return reduce(_lcm, numbers)
sys.setrecursionlimit(1000000)
INF = float('inf')
mod = 1000000007
dire4 = [(1,0), (0,1), (-1,0), (0,-1)]
dire8 = [(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)]


N, K = LI()
ab = LIR(N-1)


utov = [[] for i in range(N+1)]

for a, b in ab:
    utov[a].append(b)
    utov[b].append(a)


q = deque()

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



bfs[1] = K



child = 0
for v in utov[1]:
    if (bfs[v] == -1):
        child += 1
        bfs[v] = K - child
        q.append(v)
        


while q:
    u = q.popleft()
    
    
    child = 1
    for v in utov[u]:
        if (bfs[v] == -1):
            child += 1
            
            
            bfs[v] = K - child
            q.append(v)


ans = 1



for pattern in bfs[1:]:
    ans = ans*pattern % mod

print(ans%mod)

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
from functools import reduce
import sys
import math
import bisect
import random
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return list(map(float, sys.stdin.readline().split()))
def LS():return sys.stdin.readline().split()
def SR(n): return [list(sys.stdin.readline())[:-1] for i in range(n)]
def IR(n): return [int(sys.stdin.readline()) for i in range(n)]
def LIR(n): return [list(map(int, sys.stdin.readline().split())) for i in range(n)]
def LSR(n): return [list(map(list, sys.stdin.readline().split())) for i in range(n)]
_gcd = lambda x, y: _gcd(y, x%y) if (x%y) else y
_lcm = lambda x, y: x*y // _gcd(x, y)
def gcd(*numbers):
    return reduce(_gcd, numbers)
def lcm(*numbers):
    return reduce(_lcm, numbers)
sys.setrecursionlimit(1000000)
INF = float('inf')
mod = 1000000007
dire4 = [(1,0), (0,1), (-1,0), (0,-1)]
dire8 = [(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)]


N, K = LI()
ab = LIR(N-1)

utov = [[] for i in range(N+1)]

for a, b in ab:
    utov[a].append(b)
    utov[b].append(a)

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

bfs[1] = K

child = 0
for v in utov[1]:
    if (bfs[v] == -1):
        child += 1
        bfs[v] = K - child
        q.append(v)

while q:
    u = q.popleft()
    child = 1
    for v in utov[u]:
        if (bfs[v] == -1):
            child += 1
            bfs[v] = K - child
            q.append(v)

ans = 1

for pattern in bfs[1:]:
    ans = ans*pattern % mod

print(ans%mod)