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
import math
sys.setrecursionlimit(1000000)
mod=1000000007
class Node:
    def __init__(self):
        self.next=[]
    def get_data(self,new_next,weight=1):
        self.next.append(new_next)
def BFS(i,depth,K):  
    depth+=1
    tmp=i
    seki=1
    num=len(tmp)
    if depth==1:
        calc=K-1
        loop=range(calc,calc-num,-1)
        for i in loop:
            seki*=i%1000000007

        
    else:
        calc=K-2
        num-=1
        if calc>=num:
            seki=cache[num]
        else:
            print(0)
            exit()

            
            
    for each in tmp:
        if not check_node[each]:
            check_node[each]=True
            seki*=BFS(node[each].next,depth,K)%mod
    return seki


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

if K>2:
    cache=[0 for i in range(K-2)]
    cache[0]=1
    for i in range(1,K-2):
        cache[i]=cache[i-1]*(K-1-i)%mod
    cache.append(cache[-1])
else:
    cache=[1,1]
node=[Node() for _ in range(N)]
check_node=[False for _ in range(N)]
check_node[0]=True
for i in range(N-1):
    p,n=list(map(int,input().split()))
    node[n-1].get_data(p-1)
    node[p-1].get_data(n-1)
start=0
d=0

com=K*BFS(node[0].next,d,K)
print(int(com)%mod)

Solution (Python):
import sys
sys.setrecursionlimit(100000)
 
 
N, K = list(map(int, input().split()))
ab = []
for i in range(N-1):
    ab.append(list(map(int, input().split())))
 
ki = []
 
for i in range(N):
    ki.append(dict())
    ki[-1]["eda"] = []
 
for i in range(N-1):
    ki[ab[i][0] - 1]["eda"].append([ab[i][1] - 1])
    ki[ab[i][1] - 1]["eda"].append([ab[i][0] - 1])
 
def P(m ,n):
    if m <= 0 or n <= 0:
        return 0
    else:
        num = 1
        for i in range(n):
            num = num*(m-i) % 1000000007
        return num
 
def saiki(i, base, ki):
    num = 1
    eda_num = len(ki[i]["eda"])-1
    if eda_num == 0:
        return num
    num *= P(K-2, eda_num)
 
    for edge in ki[i]["eda"]:
        if edge[0] != base:
            num *= saiki(edge[0], i, ki)
 
    num = num % 1000000007
    return num
 
total_num = K
if len(ki[0]["eda"]) != 0:
    total_num *= P(K-1, len(ki[0]["eda"]))
    for edge in ki[0]["eda"]:
        total_num *= saiki(edge[0], 0, ki)
        total_num = total_num % 1000000007
        if total_num == 0:
            break
 
print(total_num)

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

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


def permutation(n,r):
    import math
    return math.factorial(n)//math.factorial(n-r)

cal_lst = [None] * (K)
def calc(n):
    if cal_lst[n] != None:
        return cal_lst[n]
    if n == 0:
        cal_lst[n] = 1
        return cal_lst[n]
    if n > K-2:
        return 0;
    cal_lst[n] = permutation(K-2, n)
    return cal_lst[n]

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



s = 1
Q = deque([s])
ans = K
searced = [0] * (N+1)
searced[s] = 1
cand = K-1
while len(Q) != 0:
    tmp = 1
    v = Q.popleft()
    for i in g[v]:
        if searced[i] == 1:
            continue
        else:
            searced[i] = 1
            tmp = (tmp * cand) % MOD
            cand -= 1
            Q.append(i)
    ans = (ans * tmp) % MOD
    cand = K-2
print (ans % MOD)

Solution (Python):
import sys
from collections import deque
input = sys.stdin.readline
 
N, K = list(map(int, input().split()))
ab = []
for i in range(N-1):
    ab.append(list(map(int, input().split())))
 
ki = []
 
for i in range(N):
    ki.append(dict())
    ki[-1]["eda"] = []
 
for i in range(N-1):
    ki[ab[i][0] - 1]["eda"].append([ab[i][0] - 1, ab[i][1] - 1])
    ki[ab[i][1] - 1]["eda"].append([ab[i][1] - 1, ab[i][0] - 1])
 
def P(m ,n):
    num = 1
    for i in range(n):
        num = num * (m-i) % 1000000007
    return num
 
 
 
total_num = K
judge = [False]*N
if len(ki[0]["eda"]) != 0:
    total_num *= P(K-1, len(ki[0]["eda"]))
    judge[0] = True
    node = deque([])
    for edge in ki[0]["eda"]:
        node.append(edge[1])
    while len(node) != 0:
        i = node.popleft()
        judge[i] = True
        if len(ki[i]["eda"]) > 1:
            for edge in ki[i]["eda"]:
                if not judge[edge[1]]:
                    node.append(edge[1])
        total_num *= P(K-2, len(ki[i]["eda"])-1)
        total_num = total_num % 1000000007
        if total_num == 0:
            break
 
print(total_num)

Solution (Python):
import sys

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

def P(m, n):
    num = 1
    for i in range(n):
        num = (num*(m-i)) % INF
    return num


n, k = list(map(int, sys.stdin.readline().split()))
graph = [dict() for i in range(n)]
for i in range(n):
    graph[i]["eda"]=[]
for i in range(n - 1):
    a, b = list(map(int, sys.stdin.readline().split()))
    graph[a - 1]["eda"].append(b - 1)
    graph[b - 1]["eda"].append(a - 1)
ans = 1
check = [False] * n
stack = [0]
ans = 1
while len(stack) > 0:
    x = stack.pop()
    check[x] = True
    count = 0
    for i in graph[x]["eda"]:
        if not check[i]:
            count += 1
            stack.append(i)
    if x == 0:
        temp = P(k - 1, count)
        ans = (ans * temp) % INF
    else:
        temp = P(k - 2, count)
        ans = (ans * temp) % INF

print((ans * k) % INF)

Solution (Python):
import sys

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


n, k = list(map(int, sys.stdin.readline().split()))
graph = [dict() for i in range(n)]
for i in range(n):
    graph[i]["eda"]=[]
for i in range(n - 1):
    a, b = list(map(int, sys.stdin.readline().split()))
    graph[a - 1]["eda"].append(b - 1)
    graph[b - 1]["eda"].append(a - 1)
ans = 1
check = [False] * n
stack = [0]
ans = 1
while len(stack) > 0:
    x = stack.pop()
    check[x] = True
    count = 0
    for i in graph[x]["eda"]:
        if not check[i]:
            count += 1
            stack.append(i)
    if x == 0:
        temp = 1
        for i in range(count):
            temp = temp * (k - 1 - i) % INF
        ans = ans * temp % INF
    else:
        temp = 1
        for i in range(count):
            temp = temp * (k - 2 - i) % INF
        ans = ans * temp % INF
print((ans * k) % INF)

Solution (Python):
import sys

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


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

Solution (Python):
import sys

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


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


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

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
INF=10**9+7
def LI(): return list(map(int, sys.stdin.readline().split()))
 
def main():
    n, k = LI()
    graph=[[] for i in range(n)]
    for i in range(n-1):
        a,b=LI()
        graph[a-1].append(b-1)
        graph[b-1].append(a-1)
    ans=1
    check=[False]*n
    stack=[0]
    ans=1
    while len(stack)>0:
        x=stack.pop()
        check[x]=True
        count=0
        for i in graph[x]:
            if not check[i]:
                count+=1
                stack.append(i)
        if x==0:
            temp=1
            for i in range(count):
                temp=temp*(k-1-i)%INF
            ans=ans*temp%INF
        else:
            temp=1
            for i in range(count):
                temp=temp*(k-2-i)%INF
            ans=ans*temp%INF
    print((ans*k)%INF)
 
 
if __name__ == "__main__":
    main()

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

mod=int(1e9+7)
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-=1; b-=1
  g[a].append(b); g[b].append(a);
 
dp=[-1 for x in range(n)]
def f(v,p):
  if dp[v]!=-1:
    return dp[v]

  dp[v]=1
  j=1+int(v!=0)
  for i in g[v]:
    if i!=p:
      dp[v]=(dp[v]*f(i,v)*max(k-j,0))%mod
      j+=1
  return dp[v]
 
print(f(0,-1)*k%mod)

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

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

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

for _ in range(N-1) :
    fromNode, toNode = map(int,input().split())

    fromNode -= 1
    toNode -= 1

    edge[fromNode].append(toNode)
    edge[toNode].append(fromNode)


def bfs(nowNode, fromNode) :
    colorNum = K  
    if fromNode == -1 :  
        colorNum -= 1
    else :
        colorNum -= 2

    if len(edge[nowNode]) - 1 > K :  
        return 0

    caseNum = 1
    for nextNode in edge[nowNode] :
        if nextNode == fromNode :
            continue
        caseNum *= colorNum
        colorNum -= 1
        caseNum = caseNum % MOD

    for nextNode in edge[nowNode] :
        if nextNode == fromNode :
            continue
        caseNum *= bfs(nextNode, nowNode)
        caseNum = caseNum % MOD

    return caseNum

ans = bfs(0, - 1) * K
ans = ans % MOD
print(ans)

Solution (Python):
from sys import stdin, setrecursionlimit

setrecursionlimit(10 ** 7)


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


inf = 1000000007


def main():
    N, K = LI()
    graph = [[] for _ in range(N)]
    for i in range(N - 1):
        a, b = LI()
        graph[a - 1].append(b - 1)
        graph[b - 1].append(a - 1)

    stack = [0]
    ans = 1
    done = [False] * N
    while len(stack) > 0:
        now = stack.pop()
        done[now] = True
        cnt = 0
        for x in graph[now]:
            if not done[x]:
                cnt += 1
                stack.append(x)
        if now == 0:
            for i in range(cnt):
                ans = (K - 1 - i) * ans % inf
        else:
            for i in range(cnt):
                ans = (K - 2 - i) * ans % inf
    print(ans * K % inf)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
INF=10**9+7
def LI(): return list(map(int, sys.stdin.readline().split()))
 
def main():
    n, k = LI()
    graph=[[] for i in range(n)]
    for i in range(n-1):
        a,b=LI()
        graph[a-1].append(b-1)
        graph[b-1].append(a-1)
    ans=1
    check=[False]*n
    stack=[0]
    ans=1
    while len(stack)>0:
        x=stack.pop()
        check[x]=True
        count=0
        for i in graph[x]:
            if not check[i]:
                count+=1
                stack.append(i)
        if x==0:
            temp=1
            for i in range(count):
                temp=temp*(k-1-i)%INF
            ans=ans*temp%INF
        else:
            temp=1
            for i in range(count):
                temp=temp*(k-2-i)%INF
            ans=ans*temp%INF
    print((ans*k)%INF)
 
 
if __name__ == "__main__":
    main()

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

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

MOD = 10 ** 9 + 7

g = [[] for _ in range(N)]
for a, b in AB:
	a, b = a - 1, b - 1
	g[a] += [b]
	g[b] += [a]

cn = [0] * N
def dfs(v, p):
	cn[v] = len(set(g[v]) - {p})
	for n in g[v]:
		if n == p:
			continue
		dfs(n, v)
dfs(0, -1)

r = K
for i in range(cn[0]):
	r *= K - 1 - i
	r %= MOD

for n in cn[1:]:
	for i in range(n):
		r *= K - 2 - i
		r %= MOD

print(r)

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

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from collections import deque

def main():
    n, k = li()
    MOD = 10**9 + 7
    g = [[] for _ in range(n+1)]

    for i in range(n-1):
        a, b = li()
        g[a].append(b)
        g[b].append(a)

    s = 1
    que = deque([s])
    ans = k
    qapp = que.append
    searched = [0]*(n+1)
    searched[s] = 1
    qpop = que.popleft
    cand = k-1

    while len(que):
        temp = 1
        v = qpop()

        for i in g[v]:
            if searched[i]:
                continue

            searched[i] = 1
            temp = temp * cand % MOD
            cand -= 1
            qapp(i)

        ans = ans * temp % MOD
        cand = k - 2

    print(ans % MOD)

if __name__ == "__main__":
    main()

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

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())


class Abc133eSolver(object):
    def __init__(self, n, k, mod):
        self.graph = [[] for _ in range(n)]
        self.visited = [False]*n

        self.n = n
        self.k = k
        self.mod = mod

    def construct_graph(self):
        for _ in range(self.n-1):
            a, b = li_()
            self.graph[a].append(b)
            self.graph[b].append(a)

    def dfs(self, cur, depth, nthchild):
        self.visited[cur] = True

        if depth == 0:
            used = 0 + nthchild

        elif depth == 1:
            used = 1 + nthchild

        else:
            used = 2 + nthchild

        ret = max(0, self.k - used)

        childnum = 0
        for nex in self.graph[cur]:
            if not self.visited[nex]:
                self.visited[nex] = True

                ret *= self.dfs(nex, depth + 1, childnum)
                ret %= self.mod

                childnum += 1

        return ret

n, k = li()
MOD = 10**9 + 7

solver = Abc133eSolver(n, k, MOD)

solver.construct_graph()

print(solver.dfs(0, 0, 0))

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

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

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


if __name__ == "__main__":
    main()

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

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

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


if __name__ == "__main__":
    main()

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

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

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


if __name__ == "__main__":
    main()

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

N,K = list(map(int,input().split()))
edges = [[] for _ in range(N+1)]

MOD = 1000000007

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

children = [[] for _ in range(N+1)]
seen = set()
stack = []

stack.append(1)
seen.add(1)

while stack:
    node = stack[-1]
    stack.pop()
    for edge in edges[node]:
        if edge not in seen:
            seen.add(edge)
            children[node].append(edge)
            stack.append(edge)

def solve(node, siblings, depth):
    num_children = len(children[node])

    has_grandparent = depth >= 2
    has_parent = depth >= 1

    ans = max(0, K-(siblings)-int(has_parent)-int(has_grandparent))
    child_siblings = 0
    for child in children[node]:
        ans *=  solve(child, child_siblings, depth+1)
        ans %= MOD
        child_siblings += 1
    return ans


print(solve(1, 0, 0) % MOD)

Solution (Python):
from collections import deque
n,k = map(int,input().split())
vertices = [[] for _ in range(n+1)]
visite = [[] for _ in range(n+1)]
value = [0 for _ in range(n+1) ]
c = 0
done = set()
queue = deque()
queue.append(1)
mod = 1000000007
for i in range(n-1):
    a,b = map(int,input().split())
    vertices[a].append(b)
    vertices[b].append(a)
value[1]= k
done.add(1)
while(len(queue)>0):
    next = queue.popleft()
    done.add(next)
    for v in vertices[next]:
        if v not in done:
            visite[next].append(v)
            value[v] = k - len(visite[next])
            visite[v].append(next)
            queue.append(v)
ans=1
for i in range(1,n+1):
    ans*=value[i]
    ans%=mod
print(ans)

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

def P(x, y):
    r = 1
    for i in range(y):
        r = (r * (x - i)) % mod
    return r
g=[0]*(N+1)
for v in range(N-1):
    a,b=map(int,input().split())
    g[a] += 1
    g[b] += 1
r = 1
for v in range(N-1):
    r=(P(K-2,g[v+1]-1)*r)%mod
print((K*P(K-1,g[-1])*r)%mod)

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

def P(x, y):
    r = 1
    for i in range(y):
        r = (r * (x - i)) % mod
    return r
G = [[] for _ in range(N+1)]
g=[0]*(N+1)
for v in range(N-1):
    a,b=map(int,input().split())
    G[a].append(b)
    G[b].append(a)
    g[a] += 1
    g[b] += 1
r = 1
for v in range(N-1):
    r=(P(K-2,g[v+1]-1)*r)%mod


s,V=G[1],{1}
r=P(K-1,len(s))
while len(s)!=0:
    v = s.pop()
    if v in V:continue
    V.add(v)
    s += G[v]
    r=(P(K-2,len(G[v])-1)*r)%mod
print((K*r)%mod)

Solution (Python):
from collections import deque
mod = 1000000007

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

que = deque()
que.append(0)

used = [False] * n 
used[0] = True 
ans = k

while que:
    i = que.popleft()
    if i == 0: 
        c = k-1
    else:
        c = k-2 

    for e in path[i]:
        if used[e]: continue
        used[e] = True
        ans = (ans * c) % mod 
        c -= 1
        que.append(e)

print(ans)

Solution (Python):
from collections import deque


def inpl():
    return list(map(int, input().split()))


N, K = inpl()
AB = [inpl() for i in range(N - 1)]
path1 = [[] for i in range(N)]
for a, b in AB:
    a -= 1
    b -= 1
    path1[a].append(b)
    path1[b].append(a)

flag = [False for i in range(N)]
MOD = 10**9 + 7

ans = 1
que = deque()
que.append(0)
while que:
    i = que.popleft()
    if flag[i] is True:
        sumi = 1
    else:
        sumi = 0
        flag[i] = True

    for j in path1[i]:
        if flag[j] is True:
            sumi += 1
        else:
            que.append(j)
            flag[j] = True

    
    for i in range(sumi, len(path1[i]) + 1):
        ans *= K - i
        ans %= MOD
    

print(ans % MOD)

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

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

tree=[]
for i in range(N+1):
  tree.append([])

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


answer=1
visited=[False]*(N+1)
def dfs(node,depth,cind):
  
  global answer
  visited[node]=True
  
  if depth==0:
    answer*=K
    answer%=mod
  elif depth==1:
    answer*=K-1-cind
    answer%=mod
  else:
    answer*=K-2-cind
    answer%=mod
  
  next_nodes=tree[node]
  i=0
  for nn in next_nodes:
    if not visited[nn]:
      dfs(nn,depth+1,i)
      i+=1

node=N//2
dfs(node,0,0)
print(answer)

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())
T = [[] for i in range(N)]
MOD = 10 ** 9 + 7
for i in range(N - 1):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    T[a].append(b)
    T[b].append(a)


stack = [0]
visited = [0] * N
child_num = [0] * N
while stack:
    n = stack.pop()
    visited[n] = 1
    for to in T[n]:
        if visited[to]:
            continue
        child_num[n] += 1
        stack.append(to)



factorial = [1]
inverse = [1]
for i in range(1, 10 ** 5 + 1):
    factorial.append(factorial[-1] * i % MOD)
    inverse.append(pow(factorial[-1], MOD - 2, MOD))



def nCr(n, r):
    if n < r or r < 0:
        return 0
    elif r == 0:
        return 1
    return factorial[n] * inverse[r] * inverse[n - r] % MOD


ans = K
stack = [0]
visited = [0] * N
while stack:
    n = stack.pop()
    visited[n] = 1

    if n == 0:
        ans = ans * nCr(K - 1, child_num[n]) * factorial[child_num[n]] % MOD
    else:
        ans = ans * nCr(K - 2, child_num[n]) * factorial[child_num[n]] % MOD
    for to in T[n]:
        if visited[to]:
            continue
        stack.append(to)

print(ans % MOD)

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

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

mod = 10 ** 9 + 7

import sys

sys.setrecursionlimit(10 ** 9)


def dfs(prev, now, graph):
    if prev == -1:
        mul = K - 1
    else:
        mul = K - 2

    if K < len(graph[now]):
        return 0
    else:
        tmp = 1
        for v in graph[now]:
            if v == prev:
                continue
            else:
                tmp *= mul
                mul -= 1
                tmp %= mod
                tmp *= dfs(now, v, graph)
                tmp %= mod
    return tmp

ans = K
ans *= dfs(-1, 0, graph)
print(ans % mod)

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):
N,K = map(int,input().split())
AB = [list(map(int,input().split())) for _ in [0]*(N-1)]
mod = 10**9+7

E = [[] for _ in [0]*N]
for a,b in AB:
    E[a-1].append(b-1)
    E[b-1].append(a-1)

ans = K
q = [0]
V = [False for _ in [0]*N]
V[0] = True
while q:
    qq = []
    for i in q:
        l = K-2+(i==0)
        for j in E[i]:
            if V[j]:continue
            ans = ans * l % mod
            if ans == 0:break
            qq.append(j)
            V[j] = True
            l -= 1
    q = qq
print(ans)

Solution (Python):
from functools import reduce

N, K = map(int, input().split())
a, b = (
    zip(*(map(int, input().split()) for _ in range(N - 1))) if N - 1 else
    ((), ())
)

MOD = 10**9 + 7


class ModInt:
    def __init__(self, x):
        self.x = x % MOD

    def __str__(self):
        return str(self.x)

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            ModInt(
                pow(self.x, other.x, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(pow(self.x, other, MOD))
        )

    def __radd__(self, other):
        return ModInt(other + self.x)

    def __rsub__(self, other):
        return ModInt(other - self.x)

    def __rmul__(self, other):
        return ModInt(other * self.x)

    def __rtruediv__(self, other):
        return ModInt(other * pow(self.x, MOD - 2, MOD))

    def __rpow__(self, other):
        return ModInt(pow(other, self.x, MOD))


G = [{} for _ in range(N + 1)]
for x, y in zip(a, b):
    G[x][y] = 1
    G[y][x] = 1
INF = 10**9


def p(n, r):
    return reduce(
        lambda acc, i: acc * (n - i),
        range(r),
        ModInt(1)
    )




ans = reduce(
    lambda acc, i: acc * p(K - 2, len(G[i]) - 1),
    range(2, N + 1),
    K * p(K - 1, len(G[1]))
)

print(ans)

Solution (Python):
from functools import reduce

N, K = map(int, input().split())
a, b = (
    zip(*(map(int, input().split()) for _ in range(N - 1))) if N - 1 else
    ((), ())
)

MOD = 10**9 + 7


class ModInt:
    def __init__(self, x):
        self.x = x % MOD

    def __str__(self):
        return str(self.x)

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            ModInt(
                pow(self.x, other.x, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(pow(self.x, other, MOD))
        )

    def __radd__(self, other):
        return ModInt(other + self.x)

    def __rsub__(self, other):
        return ModInt(other - self.x)

    def __rmul__(self, other):
        return ModInt(other * self.x)

    def __rtruediv__(self, other):
        return ModInt(other * pow(self.x, MOD - 2, MOD))

    def __rpow__(self, other):
        return ModInt(pow(other, self.x, MOD))


G = [{} for _ in range(N + 1)]
for x, y in zip(a, b):
    G[x][y] = 1
    G[y][x] = 1
INF = 10**9


def p(n, r):
    return reduce(
        lambda acc, i: acc * (n - i),
        range(r),
        ModInt(1)
    )



ans = reduce(
    lambda acc, i: acc * p(K - 2, len(G[i]) - 1),
    range(2, N + 1),
    K * p(K - 1, len(G[1]))
)

print(ans)

Solution (Python):
N,K = map(int,input().split())
AB = [list(map(int,input().split())) for _ in [0]*(N-1)]
mod = 10**9+7

E = [[] for _ in [0]*N]
for a,b in AB:
    E[a-1].append(b-1)
    E[b-1].append(a-1)

ans = K
q = [0]
V = [False for _ in [0]*N]
V[0] = True
while q:
    qq = []
    for i in q:
        
        
        l = K-2+(i==0)
        for j in E[i]:
            if V[j]:continue
            ans = ans * l % mod
            if ans == 0:break
            qq.append(j)
            V[j] = True
            l -= 1
    q = qq
print(ans)