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

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 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
			dp[length] = tmp
		else:
			ans *= dp[length]
		ans %= MOD

	
	print(ans%MOD)

if __name__ == '__main__':
	main()

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
			dp[length] = tmp
		else:
			ans *= dp[length]
		ans %= MOD

	
	print(ans%MOD)

if __name__ == '__main__':
	main()

Solution (Python):
import sys
sys.setrecursionlimit(1000000)
def input():
    return sys.stdin.readline()
n, k = [int(i) for i in input().split()]
e = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b = [int(i) for i in input().split()]
    a -= 1
    b -= 1
    e[a].append(b)
    e[b].append(a)
ans = 1
mod = 10**9+7
 
 
def dfs(i=0, r=-1):
    global ans
    if r == -1:
        ans *= k
        ans %= mod
 
        p = k-1
        for j in e[i]:
            if j == r:
                continue
            ans *= p
            ans %= mod
            p -= 1
            dfs(j, i)
    else:
        p = k-2
        for j in e[i]:
            if j == r:
                continue
            ans *= p
            ans %= mod
            p -= 1
            dfs(j, i)
 
 
dfs()
print(ans)

Solution (Python):
from collections import deque
import sys
sys.setrecursionlimit(10++7)

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)

mod = 10**9+7

ans = k
q = deque([])
i = 1
for nex in E[0]:
    ans *= k-i
    ans %= mod
    i += 1
    q.append((nex,0))

while q:
    now,bef =  q.popleft()
    i = 2
    for nex in E[now]:
        if nex == bef:
            continue
        ans *= k-i
        ans %= mod
        i += 1
        q.append((nex,now))
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(1000000)
def input():
    return sys.stdin.readline()
n, k = [int(i) for i in input().split()]
e = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b = [int(i) for i in input().split()]
    a -= 1
    b -= 1
    e[a].append(b)
    e[b].append(a)
ans = 1
mod = 10**9+7


def dfs(i=0, r=-1):
    global ans
    if r == -1:
        ans *= k
        ans %= mod

        p = k-1
        for j in e[i]:
            if j == r:
                continue
            ans *= p
            ans %= mod
            p -= 1
            dfs(j, i)
    else:
        p = k-2
        for j in e[i]:
            if j == r:
                continue
            ans *= p
            ans %= mod
            p -= 1
            dfs(j, i)


dfs()
print(ans)

Solution (Python):
N,K=map(int,input().split())
Tree=[[] for i in range(N)]
MOD=10**9+7
import sys
sys.setrecursionlimit(10**9)
for i in range(N-1):
  a,b=map(int,input().split())
  Tree[a-1].append(b-1)
  Tree[b-1].append(a-1)
def P(n,m):
  _=n
  for i in range(m-1):
    n-=1
    _*=n
    _%=MOD
  return _%MOD
def dfs(p,i):
  global Tree,ans
  n=len(Tree[i])-1
  if n==0:
    return
  if i==0:
    ans*=P(K-1,n)
  else:
    ans*=P(K-2,n)
    ans%=MOD
  for j in Tree[i]:
    if j==p:
      continue
    dfs(i,j)
Tree[0].append(-1)
ans=K
dfs(-1,0)
print(ans%MOD)

Solution (Python):
n,k = map(int,input().split())
mod = 10**9 + 7
path = [set() for _ in range(n)]
for i in range(n-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    path[a].add(b)
    path[b].add(a)
fac = [1]*(k+2)
fac_inv = [1]*(k+2)
for i in range(1,k+2):
    fac[i] = fac[i-1] * i %mod
    fac_inv[i] = pow(fac[i],mod-2,mod)

def P(n,k):
    if n-k < 0:
        print(0)
        exit()
    return fac[n] * fac_inv[n-k] %mod

ans = 1
reach = [False] * n
reach[0] = True
que = []
for i in path[0]:
    que.append(i)
ans *= P(k,len(path[0])+1)
while que:
    p = que.pop()
    reach[p] = True
    ans *= P(k-2,len(path[p])-1)
    ans %= mod
    for i in path[p]:
        if not reach[i]:
            que.append(i)
print(ans)

Solution (Python):
import sys,heapq

mod = 10**9+7 
N = 2*10**5
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())
hen={i:[] for i in range(1,N+1)}
for i in range(0,N-1):
    a,b=map(int,input().split())
    hen[a].append(b)
    hen[b].append(a)

parent={i:-1 for i in range(1,N+1)}
parent[1]=0
q=[1]
heapq.heapify(q)
sub=[]
heapq.heapify(sub)
while q:
    while q:
        x=heapq.heappop(q)
        for p in hen[x]:
            if parent[p]==-1:
                parent[p]=x
                heapq.heappush(sub,p)
        
        
        if q==[]:
            q=sub
            sub=[]
            heapq.heapify(sub)
            break

ans={i:1 for i in range(1,N+1)}
flag={i:0 for i in range(1,N+1)}
q=[]
for i in range(1,N+1):
    if i!=1 and len(hen[i])==1:
        q.append(i)
sub=[]
heapq.heapify(sub)
while q:
    while q:
        x=heapq.heappop(q)
        p=parent[x]
        if p!=1:
            if len(hen[p])-1>K-2:
                ans[p]=0
            else:
                ans[p]=(ans[p]*ans[x])%mod
            flag[p]+=1
            if flag[p]==len(hen[p])-1:
                ans[p]=(ans[p]*g1[K-2]*g2[K-2-flag[p]])%mod
                heapq.heappush(sub,p)
        
        
        if q==[]:
            q=sub
            sub=[]
            heapq.heapify(sub)
            break

if len(hen[1])>K-1:
    print(0)
else:
    for i in hen[1]:
        ans[1]=(ans[1]*ans[i])%mod
    ans[1]=(ans[1]*g1[K]*g2[K-1-len(hen[1])])%mod
    print(ans[1])

Solution (Python):


MOD = 10**9 + 7
N,K = map(int, input().split())
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]







ans = (K * nPr(K-1, len(es[0]))) % MOD
stack = []
for nxt in es[0]:
    stack.append(nxt)

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


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

print(ans % MOD)

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

mod = 10**9 + 7

n,k = map(int,input().split())
if(n == 1):
    print(k)
    exit()


edges = {}
d = [0] * (n+1)
for i in range(1,n+1):
    edges[i] = []

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

for i in range(1,n+1):
    if(d[i] == 1):
        first = i
        break

d = [0] * (n+1)
d[0] = -1
d[first] = -1
dq = deque()
dq.appendleft([0,first])

ans = 1
while(len(dq) > 0):
    parent, child = dq.pop()
    d[parent] += 1
    d[child] += 1
    ans = ans * (k - d[parent]) % mod

    for i in edges[child]:
        if(i != parent):
            dq.appendleft([child, i])

print(ans)

Solution (Python):
import sys


from collections import Counter, deque











readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


class Edge:

    def __init__(self, index, u, v):
        self.index = index
        self.u = u
        self.v = v

    def __str__(self):
        return "{} {}".format(self.u, self.v)


class Vertex:

    def __init__(self, index):
        self.index = index
        self.connected_edge_index = []
        self.color = -1

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


class Graph:
    

    def __init__(self, vertices=0):
        self.vertices = [Vertex(x) for x in range(vertices + 1)]
        self.edges = []
        self._vertex_count = vertices
        self._edges_count = 0

    def edges_count(self):
        return self._edges_count

    def vertices_count(self):
        return self._vertices_count

    def add_edge(self, u, v):
        edge = Edge(self._edges_count, u, v)
        self.vertices[edge.u].connected_edge_index.append(edge.index)
        self.vertices[edge.v].connected_edge_index.append(edge.index)
        self.edges.append(edge)
        self._edges_count += 1

    
    def neighbors(self, index):
        return [self.edges[e].u if self.edges[e].u != index else self.edges[e].v for e in
                self.vertices[index].connected_edge_index]

    
    def neighbors_count(self, index):
        return len(self.vertices[index].connected_edge_index)

    def __str__(self):
        desc = ""
        for i in range(self._edges_count):
            desc += str(self.edges[i]) + "\n"
        return desc


def main():
    n, k = list(map(int, readline().split()))
    g = Graph(n)

    for i in range(n-1):
        a, b = list(map(int, readline().split()))
        g.add_edge(a, b)

    que = deque()
    que.append((1, 0, k))

    while que:
        current, parent, c = que.popleft()
        g.vertices[current].color = c
        next_c = k - 1 - parent
        for i in g.neighbors(current):
            if g.vertices[i].color == -1:
                que.append((i, 1, next_c))
                next_c -= 1

    ans = 1

    for i in range(1, n + 1):
        ans *= g.vertices[i].color
        ans %= MOD

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys


from collections import Counter, deque











readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


class Edge:

    def __init__(self, index, u, v):
        self.index = index
        self.u = u
        self.v = v

    def __str__(self):
        return "{} {}".format(self.u, self.v)


class Vertex:

    def __init__(self, index):
        self.index = index
        self.connected_edge_index = []
        self.color = -1

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


class Graph:
    

    def __init__(self, vertices=0):
        self.vertices = [Vertex(x) for x in range(vertices + 1)]
        self.edges = []
        self._vertex_count = vertices
        self._edges_count = 0

    def edges_count(self):
        return self._edges_count

    def vertices_count(self):
        return self._vertices_count

    def add_edge(self, u, v):
        edge = Edge(self._edges_count, u, v)
        self.vertices[edge.u].connected_edge_index.append(edge.index)
        self.vertices[edge.v].connected_edge_index.append(edge.index)
        self.edges.append(edge)
        self._edges_count += 1

    
    def neighbors(self, index):
        return [self.edges[e].u if self.edges[e].u != index else self.edges[e].v for e in
                self.vertices[index].connected_edge_index]

    
    def neighbors_count(self, index):
        return len(self.vertices[index].connected_edge_index)

    def __str__(self):
        desc = ""
        for i in range(self._edges_count):
            desc += str(self.edges[i]) + "\n"
        return desc


def main():
    n, k = list(map(int, readline().split()))
    g = Graph(n)

    for i in range(n-1):
        a, b = list(map(int, readline().split()))
        g.add_edge(a, b)

    que = deque()
    que.append((1, 0, k))

    while que:
        current, parent, c = que.popleft()
        g.vertices[current].color = c
        next_c = k - 1 - parent
        for i in g.neighbors(current):
            if g.vertices[i].color == -1:
                que.append((i, 1, next_c))
                next_c -= 1

    ans = 1

    for i in range(1, n + 1):
        ans *= g.vertices[i].color
        ans %= MOD

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):

import sys
sys.setrecursionlimit(100000)
mod = 10 ** 9 + 7
n, k = map(int, input().split())
edges = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = map(int, input().split())
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)
    
def dfs(frm, cur):
    if frm == -1:
        color_num = k - 1
    else:
        color_num = k - 2
        
    mul = 1
    for to in edges[cur]:
        if to == frm:
            continue
        mul *= color_num
        mul %= mod
        color_num -= 1
        
    for to in edges[cur]:
        if to == frm:
            continue
        mul *= dfs(cur, to)
        mul %= mod
    
    return mul

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

Solution (Python):

import sys
sys.setrecursionlimit(100000)
mod = 10 ** 9 + 7
n, k = map(int, input().split())
edges = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = map(int, input().split())
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)
    
def dfs(frm, cur):
    if frm == -1:
        color_num = k - 1
    else:
        color_num = k - 2
        
    if k < len(edges[cur]):
        return 0
    
    mul = 1
    for to in edges[cur]:
        if to == frm:
            continue
        mul *= color_num
        mul %= mod
        color_num -= 1
        
    for to in edges[cur]:
        if to == frm:
            continue
        mul *= dfs(cur, to)
        mul %= mod
    
    return mul

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

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

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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


PATH = [[] for _ in range(N + 1)]

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


DONE = [False] * (N+1)

ans = K
q = [(1, 0)]
while q:
    u, cnt = q.pop()
    DONE[u] = True
    i = 0
    for v in PATH[u]:
        if u == v or DONE[v]:
            continue
        ans *= K - i - 1 - cnt
        ans %= MOD
        q.append((v, 1))
        i += 1


print(ans)

Solution (Python):

from collections import Counter, deque



import itertools



import sys



readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


class Node:

    def __init__(self, nid):
        self.node_id = nid
        self.color = -1
        self.next = []


def main():
    n, k = list(map(int, readline().split()))

    nodes = [Node(i) for i in range(n)]

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

    que = deque()
    que.append((0, 0, 0))

    while que:
        current_id, cn_1, cn_2 = que.popleft()

        cl = k - cn_1 - cn_2

        if cl <= 0:
            print(0)
            sys.exit()

        nodes[current_id].color = cl

        for nid in nodes[current_id].next:
            if nodes[nid].color == -1:
                cn_1 += 1
                que.append((nid, 1, cn_1 - 1))

    ans = 1
    for i in range(n):
        ans *= nodes[i].color
        ans %= MOD

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
n,k=map(int,input().split())
ab=[[] for i in range(n+1)]
for i in range(n-1):
  a,b=map(int,input().split())
  ab[a]+=[[b,a]]
  ab[b]+=[[a,b]]
x=k
c=[]+ab[1]
d=[0]*(n+1)
while c:
  y,z=c.pop()
  c+=[i for i in ab[y] if i[0]!=z]
  x=(x*max(0,k-1-d[z]))%(10**9+7)
  d[z]+=1
  d[y]=1
print(x)

Solution (Python):
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7

n,k=map(int,input().split())
ab=[list(map(int,input().split())) for i in range(n-1)]

dic=defaultdict(list)
for i in range(n-1):
    a,b=ab[i]
    dic[a].append(b)
    dic[b].append(a)


itta=[0]*(n+1)
itta[1]=1
d=deque([[1,0,0]])

ans=k
while d:
    tmp=d.popleft()
    now,one,two=tmp
    j=0
    for i in range(len(dic[now])):
        if itta[dic[now][i]]==0:
            itta[dic[now][i]]=1
            ans*=k-1-two-j
            j+=1
            d.append([dic[now][i],one,one+1])
            ans%=mod
    

print(ans)

Solution (Python):
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

MOD = 10 ** 9 + 7

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

def cumprod(arr, MOD):
    L = len(arr); Lsq = int(L**.5+1)
    arr = np.resize(arr, Lsq**2).reshape(Lsq, Lsq)
    for n in range(1, Lsq):
        arr[:, n] *= arr[:, n-1]; arr[:, n] %= MOD
    for n in range(1, Lsq):
        arr[n] *= arr[n-1, -1]; arr[n] %= MOD
    return arr.ravel()[:L]

def make_fact(U, MOD):
    x = np.arange(U, dtype=np.int64); x[0] = 1
    fact = cumprod(x, MOD)
    x = np.arange(U, 0, -1, dtype=np.int64); x[0] = pow(int(fact[-1]), MOD-2, MOD)
    fact_inv = cumprod(x, MOD)[::-1]
    return fact, fact_inv

def permutation(n, x, mod=10**9+7):
    
    tmp = 1
    for i in range(n, n-x, -1):
        tmp = (tmp * i) % mod
    return tmp

U = 10 ** 5 + 10 
fact, fact_inv = make_fact(U, MOD)

N, K = lr()
graph = [[] for _ in range(N+1)] 
for _ in range(N-1):
    a, b = lr()
    graph[a].append(b)
    graph[b].append(a)

answer = K 
if K-1-len(graph[1]) < 0:
    answer = 0
else:
    answer *= fact[K-1] * fact_inv[K-1-len(graph[1])] % MOD
answer %= MOD
root = 1
stack = []
for child in graph[1]:
    if len(graph[child]) > 1:
        stack.append((child, 1))
while stack:
    cur, p = stack.pop()
    l = len(graph[cur])
    if K-2-(len(graph[cur])-1) < 0:
        answer = 0
    elif l > 1:
        answer *= fact[K-2] * fact_inv[K-2-(len(graph[cur])-1)] % MOD
    for child in graph[cur]:
        if child == p:
            continue
        stack.append((child, cur))
    answer %= MOD

print(answer%MOD)

Solution (Python):
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

MOD = 10 ** 9 + 7

def permutation(n, x, mod=10**9+7):
    
    tmp = 1
    for i in range(n, n-x, -1):
        tmp = (tmp * i) % mod
    return tmp

N, K = lr()
graph = [[] for _ in range(N+1)] 
for _ in range(N-1):
    a, b = lr()
    graph[a].append(b)
    graph[b].append(a)

answer = K 
answer *= permutation(K-1, len(graph[1])) % MOD
root = 1
stack = []
for child in graph[1]:
    if len(graph[child]) > 1:
        stack.append((child, 1))
while stack:
    cur, p = stack.pop()
    l = len(graph[cur])
    if l > 1:
        answer *= permutation(K-2, len(graph[cur])-1) % MOD
    for child in graph[cur]:
        if child == p:
            continue
        if len(graph[child]) > 1:
            stack.append((child, cur))
    answer %= MOD

print(answer%MOD)

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

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

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

color = [-1]*n
ans = k

def bfs(u):
    global ans
    queue = deque([u])
    color[u] = k
    while queue:
        v = queue.popleft()
        cnt = 0
        if v == 0:
            start = k - 1
        else:
            start = k -2
        for i in g[v]:
            if color[i] < 0:
                color[i] = start - cnt
                cnt += 1
                ans *= color[i]
                ans %= mod
                queue.append(i)

bfs(0)
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
n,k = map(int,input().split())
ki = [[]for _ in range(n)]
mod = 10**9+7
fact = [1]*(max(n,k)+1)
for i in range(1,max(n,k)+1):
    fact[i] = (fact[i-1]*i)%mod
invfact = [1]*(max(n,k)+1)
invfact[-1] = pow(fact[-1],mod-2,mod)
for i in range(max(n,k)-1,0,-1):
    invfact[i] = (invfact[i+1]*(i+1))%mod

def P(a,b,mod):
    return (fact[a]*invfact[a-b])%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)

    

def dfs(now,last = -1):
    res = 1
    
    if last != -1:
        if len(ki[now]) == 1:return 1
        res = P(k-2,len(ki[now])-1,mod)
        if k-1 < len(ki[now]):res = 0
    for next in ki[now]:
        if next == last:continue
        res *= dfs(next,now)
    return res
ans = dfs(0,-1)

ans *= P(k,len(ki[0])+1,mod)
ans %= mod
if(len(ki[0])+1>k):ans = 0
print(ans)

Solution (Python):
from collections import deque
n,k=map(int,input().split())
edge=[[] for _ in range(n)]
visited=[-1]*n
def pmt(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    return g1[n]* g2[n-r] % mod

mod = 10**9+7 
N = 10**5
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 )
for _ in range(n-1):
  a,b=map(int,input().split())
  a-=1
  b-=1
  edge[a].append(b)
  edge[b].append(a)
stack=deque([])
visited[0]=0
for e in edge[0]:
  stack.append(e)
  visited[e]=0
def dfs():
  ans=k*pmt(k-1,len(edge[0]),mod)%mod
  while stack:
    p=stack.pop()
    cnt=0
    for c in edge[p]:
      if visited[c]==-1:
        cnt+=1
        visited[c]=0
        stack.append(c)
    ans=ans*pmt(k-2,cnt,mod)%mod
  return ans%mod
print(dfs())

Solution (Python):
import sys
 
from collections import deque
 
def LI():
	return [ int(s) for s in input().split() ]
 
N,K =LI()
tree = {}
for i in range(N):
  tree[i] = []
 
MOD = (10**9)+7
color = K
 
for _ in range(N-1):
    a,b = LI()
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)
    
 

search_candidate = deque([0])
visited = [False]*N
hierarchy = [-1]*N
hierarchy[0] = 1
for t in tree[0]:
    if t != 0:
        hierarchy[t] = 2

while search_candidate:
    search = search_candidate.popleft()
    if hierarchy[search] == 1:
        cnt = K - 1
    else:
        cnt = K - 2
    visited[search] = True
    
    for child in tree[search]:
        if visited[child]:
            continue 
 
        if cnt <= 0:
            print(0)
            sys.exit()
 
        color = (color*cnt) % MOD
        cnt -= 1
        search_candidate.appendleft(child)
      
print(color)

Solution (Python):
import sys

from collections import deque

def LI():
	return [ int(s) for s in input().split() ]

N,K =LI()
tree = {}
for i in range(N):
  tree[i] = []

MOD = (10**9)+7
color = K

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


search_candidate = deque([0])
visited = [False]*N
hierarchy = [-1]*N
hierarchy[0] = 1
for t in tree[0]:
    if t != 0:
        hierarchy[t] = 2

while search_candidate:
    search = search_candidate.pop()
    if hierarchy[search] == 1:
        cnt = K - 1
    else:
        cnt = K - 2
    visited[search] = True
    
    for child in tree[search]:
        if visited[child]:
            continue 

        if cnt <= 0:
            print(0)
            sys.exit()

        color = (color*cnt) % MOD
        cnt -= 1
        search_candidate.appendleft(child)

print(color)

Solution (Python):
n, k = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n - 1)]
mod = 10 ** 9 + 7


def p(x, y):
    ret = 1
    for i in range(y):
        ret *= x - i
        ret %= mod

    return ret


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


def dfs(s):
    d = [-1] * n
    d[s] = 0
    child = [0] * n
    stack = [s]
    while stack:
        u = stack.pop()
        for v in adj[u]:
            if d[v] == -1:
                child[u] += 1
                d[v] = d[u] + 1
                stack.append(v)

    return child


c = dfs(0)
ans = 1
for i, e in enumerate(c):
    if i == 0:
        ans *= k * p(k - 1, e)
    else:
        ans *= p(k - 2, e)

    ans %= mod

print(ans)

Solution (Python):
N,K=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(N-1)]
mod=10**9+7
fac=[1,1]
for i in range(2,K+1):
    fac.append(fac[i-1]*i%mod)
ifac=[pow(i,mod-2,mod) for i in fac]
def perm(a,b):
    if b==0:
        return(1)
    if a<b:
        return(0)
    return(fac[a]*ifac[a-b]%mod)



data=[[] for i in range(N+1)]
for a,b in AB:
    data[a].append(b)
    data[b].append(a)

"""
for i in range(1,N):
    if len(data[i])==1:
        stack=[[i,0]]
        break"""
stack=[[1,0]]
visited=set([stack[0][0]])
count=K
while stack:
    a,m=stack.pop()
    c=0
    for p in data[a]:
        if not p in visited:
            visited.add(p)
            c+=1
            stack.append([p,1])
    if c:
        count=count*perm((K-2) if m else (K-1),c)%mod

print(count)

Solution (Python):
import sys

sys.setrecursionlimit(100000)

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

mod = 1000000007
def dfs(v, p, c):
    ret = max(k - c, 0)
    used = 1 + (1 if p >= 0 else 0)
    for w in edges[v]:
        if w != p:
            ret = (ret * dfs(w, v, used)) % mod
            used += 1
    return ret
print(dfs(0, -1, 0))

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(10**7)

MOD = 10**9+7

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

cnt = [0] * n
def dfs(v, p=-1):
    if p == -1:
        n_cnt = 1
    else:
        n_cnt = 2
    for u in to[v]:
        if u == p:
            continue
        cnt[u] = n_cnt
        n_cnt += 1
        dfs(u, v)
    return cnt

ans = 1
for i in dfs(0):
  ans *= max(0, k-i)
  ans %= MOD

print(ans)

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

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

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

ans=k   
def dfs(i,before=-1):
    global ans 

    if i==0:
        j=1
    else:
        j=2
        
    for e in tree[i]:
        if e!=before:
            ans*=(k-j)
            ans%=MOD
            j+=1
            dfs(e,i)
dfs(0)
print(ans)

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

mod = 10**9+7
N, K = map(int, input().split())
G = [[] for _ in range(N+1)]
for _ in range(N-1):
    a, b = map(int, input().split())
    G[a].append(b)
    G[b].append(a)
visited = [False] * (N+1)
visited[1] = True
queue = deque()
queue.append(1)
ans = K
while queue:
    u = queue.popleft()
    n = K - 1 if u == 1 else K - 2
    for v in G[u]:
        if not visited[v]:
            queue.append(v)
            visited[v] = True
            ans = ans * n % mod
            n -= 1
print(ans)

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

def main():
    N,K = map(int,input().split())
    edge = [[] for _ in range(N)]
    for _ in range(N-1):
        a,b = map(int,input().split())
        edge[a-1].append(b-1)
        edge[b-1].append(a-1)
        
    go = [False for _ in range(N)]
    go[0] = True
    for num in edge[0]:
        go[num] = True
    MOD = 10**9+7
    fac = [0 for _ in range(K+1)]
    fac[0],fac[1] = 1,1
    inv = copy.deepcopy(fac)
    invfac = copy.deepcopy(fac)
    
    for i in range(2,K+1):
        fac[i] = (fac[i-1]*i)%MOD
        inv[i] = MOD-(MOD//i)*inv[MOD%i]%MOD
        invfac[i] = (invfac[i-1]*inv[i])%MOD
        
    def per(x,y):
        num = ((fac[x]*invfac[x-y])%MOD)
        return num

    if K-1 < len(edge[0]):
        print(0)
        exit()
    ans = K*(per(K-1,len(edge[0])))

    q = deque(edge[0])
    while q:
        now = q.popleft()
        use = 0
        for fol in edge[now]:
            if not go[fol]:
                use += 1
                go[fol] = True
                q.append(fol)
        if use > K-2:
            print(0)
            exit()
        num = per(K-2,use)
        ans *= num
        ans %= MOD
        
    print(ans%MOD)

if __name__ == "__main__":
    main()