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
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))



def edges_to_pt(s,t,n,directed=False):
    pt = [[] for _ in range(n)]
    for i in range(len(s)):
        pt[s[i]-1].append(t[i]-1)
        if directed==False:
            pt[t[i]-1].append(s[i]-1)
    return pt

def fact_all(n,M=mod):
    f = [1]*(n)
    ans = 1
    for i in range(1,n):
        ans = ans*i
        ans = ans%M
        f[i] = ans
    return f

def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    return [w[0],w[1]]

def mod_inv(a,M=mod):
    x = extgcd(a,M)[0]
    return (M+x%M)%M

N,K = II()
if N==1:
    print(K)
    exit()
else:
    a,b = Line(N-1)

pt = edges_to_pt(a,b,N)
v = 0
ans = K
check_visited = [False]*N
check_visited[v] = True
S = [v]
l = 0

f = fact_all(K)
inv = [0]*K
for i in range(K):
    inv[i] = mod_inv(f[i])

while S:
    v1 = S.pop()
    num = 0
    for i in pt[v1]:
        if check_visited[i] == False:
            check_visited[i] = True
            num += 1
            S.append(i)
    if l==0:
        if K-1-num>=0:
            ans *= f[K-1]*inv[K-1-num]
            ans %= mod
            l = 1
        else:
            print(0)
            exit()
    else:
        if K-2-num>=0 and K-2>=0:
            ans *= f[K-2]*inv[K-2-num]
            ans %= mod
        else:
            print(0)
            exit()

print(ans)

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from functools import reduce


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007



from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n, k = LI()
graph = [[] for _ in range(n)]
for a, b in LIR(n-1):
    graph[a - 1] += [b - 1]
    graph[b - 1] += [a - 1]


L = [-1] * n
check = [0] * n
L[0] = k
que = deque([0])
while que:
    cur = que.popleft()
    for nxt in graph[cur]:
        if L[nxt] == -1:
            if check[cur]:
                ret -= 1
                L[nxt] = ret % mod
                que += [nxt]
                continue
            elif cur == 0:
                ret = k - 1
            else:
                ret = k - 2
            L[nxt] = ret % mod
            que += [nxt]
            check[cur] = 1
            que += [nxt]



print(reduce(lambda x, y: x * y % mod, L))

Solution (Python):
from sys import stdin
from collections import deque

N, K = [int(x) for x in stdin.readline().rstrip().split()]
AB = [[int(x) for x in stdin.readline().rstrip().split()] for _ in range(N - 1)]

tree = [[] for _ in range(N)]
inf = 10 ** 9 + 7

for i in range(N - 1):
    tree[AB[i][0] - 1].append(AB[i][1] - 1)
    tree[AB[i][1] - 1].append(AB[i][0] - 1)

ans = 1
q = deque([0])
visited = [False] * N

while len(q) > 0:
    c = q.popleft()
    visited[c] = True
    if c == 0:
        m = K - 1
        ans *= K
        ans %= inf
    else:
        m = K - 2
    for i in range(len(tree[c])):
        if not visited[tree[c][i]]:
            ans *= m
            ans %= inf
            m -= 1
            q.append(tree[c][i])

print(ans)

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

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

perm = [0] * (10**5)
perm[0] = 1
for l in range(1,10 ** 5):
    perm[l] = (perm[l-1] * (K-l-1)) % MOD

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

def intminus(t):
    return int(t)-1

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

count = 1

for j in range(1+len(info[0])):
    count = (count * (K-j)) % MOD

stack = []
for p in info[0]:
    stack.append([0,p])

while stack:
    x = stack.pop(-1)
    count = (count * perm[len(info[x[1]])-1]) % MOD
    for xx in info[x[1]]:
        if xx == x[0]:continue
        stack.append([x[1],xx])

print(count)

Solution (Python):
from collections import defaultdict, deque

MOD = int(1e9+7)
N, K = map(int, input().split())

E = defaultdict(list)
for i in range(N-1):
    a, b = map(int, input().split())
    E[a].append(b)
    E[b].append(a)
visited = [False] * N
q = deque()
q.append(1)
visited[0] = True
ans = K
while q:
    now = q.pop()
    if now == 1:
        available = K-1
    else:
        available = K-2
    for nxt in E[now]:
        if not visited[nxt-1]:
            if available <= 0:
                print(0)
                exit()
            ans = (ans * available) % MOD
            available -= 1
            q.append(nxt)
            visited[nxt - 1] = True
print(ans)

Solution (Python):
import collections
def main():

    N, K = map(int, input().split())
    if K == 1:
        if N == 1: return 1
        else: return 0

    tree = collections.defaultdict(list)
    for _ in range(N-1):
        a, b = map(int, input().split())
        tree[a].append(b)
        tree[b].append(a)
    mod = pow(10, 9) + 7

    v = inv_factorial(K-1, mod)
    invf = [v]
    for i in range(K-1, 0, -1):
        invf.append((invf[-1] * i) % mod)
    invf = invf[::-1]

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

    ans = K
    cur = []
    visited = set([1])
    for b in tree[1]:
        cur.append(b)
        visited.add(b)
    l = len(cur)
    if l > K-1: return 0
    ans *= (f[K-1]*invf[K-1-l]) % mod
    ans %= mod

    while cur:
        temp = []
        for a in cur:
            l = len(tree[a])-1
            if l > K-2: return 0
            ans *= (f[K-2]*invf[K-2-l]) % mod
            ans %= mod
            for b in tree[a]:
                if b not in visited:
                    temp.append(b)
                    visited.add(b)
        cur = temp

    return ans


def quickpow(x, y, mod):
    if y == 0: return 1
    elif y == 1: return x
    elif y % 2 == 0: return pow(quickpow(x, y//2, mod), 2) % mod
    elif y % 2 == 1: return (pow(quickpow(x, y//2, mod), 2) * x) % mod

def factorial(x, mod):
    v = 1
    for i in range(2, x+1):
        v *= i
        v %= mod
    return v

def inv_factorial(x, mod):
    v = factorial(x, mod)
    return quickpow(v, mod-2, mod)


if __name__ == '__main__':
    print(main())

Solution (Python):
n,k=map(int,input().split())
s=[[]for i in range(n+1)]
for i in range(n-1):
    a,b=map(int,input().split())
    s[a].append(b)
    s[b].append(a)
d=[False]*(n+1)
q=[[0,1]]
c=0
a=k
while q:
    t=[]
    c=0
    for i,j in q:
        c=0
        for p in s[j]:
            if p!=i:
                t.append([j,p])
                c+=1
        r=(k-1 if j==1 else k-2)
        for h in range(r,r-c,-1):
            a=(a*h)%(10**9+7)
    q=t
print(a)

Solution (Python):
p = 10 ** 9 + 7
def f(n):
  F = [1] * (n + 1)
  for i in range(n):
    F[i + 1] = F[i] * (i + 1) % p
  return F
def finv(F):
  n = len(F) - 1
  Finv = list(F)
  Finv[n] = pow(F[n], p - 2, p)
  for i in range(n, 0, -1):
    Finv[i - 1] = Finv[i] * i % p
  return Finv
def P(n, k):
  if n < k:
    return 0
  return F[n] * Finv[n - k] % p
N, K = map(int, input().split())
E = [[] for i in range(N)]
for _ in range(N - 1):
  a, b = map(int, input().split())
  E[a - 1].append(b - 1)
  E[b - 1].append(a - 1)
F = f(K)
Finv = finv(F)
cnt = K
V = [0] * N
Q = [0] * N
pos = 1
for i in range(N):
  q = Q[i]
  V[q] = 1
  children = 0
  parent = 0
  for adj in E[q]:
    if V[adj]:
      parent += 1
    else:
      children += 1
      Q[pos] = adj
      pos += 1
  cnt *= P(K - 1 - parent, children)
  cnt %= p
print(cnt)

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

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

def dfs(now,pre):
    available_color = 0  
    if pre == -1:
        available_color = k-1
    else:
        available_color = k-2
    if k < len(graph[now]):
        return 0
    res = 1
    for son in graph[now]:
        if son == pre:continue
        res *= available_color
        available_color -= 1
        res %= MOD
    for son in graph[now]:
        if son == pre:continue
        res *= dfs(son,now)
        res %= MOD

    return res

ans = (k*dfs(0,-1)) % MOD
print(ans)

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

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

def dfs(now,pre):
    available_color = 0  
    if pre == -1:
        available_color = k-1
    else:
        available_color = k-2
    if k < len(graph[now]):
        return 0
    res = 1
    for son in graph[now]:
        if son == pre:continue
        res *= available_color
        available_color -= 1
        res %= MOD
    for son in graph[now]:
        if son == pre:continue
        res *= dfs(son,now)
        res %= MOD

    return res

ans = (k*dfs(0,-1)) % MOD
print(ans)

Solution (Python):
from collections import defaultdict as dd
from math import factorial
mod = 10 ** 9 + 7

def P(n, r):
  if r > n:
    return 1
  elif r == 0:
    return 1
  else:
    return(factorial(n) // factorial(n-r))
N, K = map(int, input().split())
D = dd(list)
for i in range(N-1):
  a, b = map(int, input().split())
  D[a-1].append(b-1)
  D[b-1].append(a-1)

Q = [0]
vstd = set()
ans = K
while Q:
  a = Q.pop()
  vstd.add(a)

  if a == 0:
    num = K-1
  else:
    num = K-2
  for b in D[a]:

    if b not in vstd:
      if num <= 0 : ans = 0
      ans = (ans * num) % mod

      num -= 1
      Q.append(b)


print (ans % mod)

Solution (Python):
import sys

mod = 1000000007

n, k = map(int, input().split())
nexts = [[] for _ in range(n+1)]
for i in range(n-1):
    a, b = map(int, sys.stdin.readline().split())
    nexts[a].append(b)
    nexts[b].append(a)


scores = [[0, 0] for _ in range(n+1)]
result = 1
nextList = [1]
while len(nextList) > 0:
    i = nextList.pop()
    defined = 0
    for j in nexts[i]:
        if scores[j][0] != 0:
            defined += scores[j][1]
        else:
            nextList.append(j)
        scores[j][1] += 1
    if k - defined <= 0:
        result = 0
        break
    result = result * (k-defined) % mod
    scores[i][0] = k-defined
    scores[i][1] += 1

print(result)

Solution (Python):
from sys import exit, stderr, stdin, setrecursionlimit
input = stdin.readline
setrecursionlimit(10**7)
def debug(var, name="hoge"):
    print(name +":" + str(type(var)) + " = " + repr(var), file=stderr)
    return




MOD = 10**9+7
NUM = 10**5 + 2

fact = [1] * (NUM + 1)
fact_inv = [1] * (NUM + 1)

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

fact_inv[NUM] = pow(fact[NUM], MOD-2, MOD)


for i in range(NUM, 2, -1):
    fact_inv[i-1] = (fact_inv[i]*i) % MOD

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



def main():
    N, K = map(int,input().split())

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

    def count(n, parent = None):
        
        if parent is None:
            c = perm(K,deg[n]+1)
        
        else:
            c = perm(K-2,deg[n]-1)
        for neigh in adjl[n]:
            if neigh == parent:
                continue
            c *= count(neigh,n)
            c %= MOD
        return c
    print(count(0))





if __name__ == "__main__":
    main()

Solution (Python):
from collections import defaultdict

mod = pow(10, 9) + 7

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

graph = defaultdict(list)

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

def dfs(v):
	global graph, k
	ans = k	
	stack = [v]
	vis_set = {v, }

	while stack:
		v = stack.pop()
		if v==0: 
			avail_count = k-1
		else: 
			avail_count = k-2
		for nxt in graph[v]:
			if nxt not in vis_set:
				if avail_count <= 0:
					return 0
				ans = (ans*avail_count)%mod
				avail_count -= 1
				stack.append(nxt)
				vis_set.add(nxt)
	return ans

ans = dfs(0)
print(ans)

Solution (Python):
import collections, queue, sys
n, k =  map(int, input().split())
m = 10**9+7
edges = collections.defaultdict(list)
q = queue.Queue()
preq = queue.Queue()
ans = 1

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

j = 1
for i in edges[1]:
    q.put(i)
    preq.put(1)
    if k - j <= 0:
        print(0)
        sys.exit()
    ans = ans%m * (k - j)%m
    j+=1

while not q.empty():
    j = 2
    node = q.get()
    prenode = preq.get()
    for i in edges[node]:
        if not i == prenode:
            q.put(i)
            preq.put(node)
            if k - j <= 0:
                print(0)
                sys.exit()
            ans = ans%m * (k - j)%m
            j+=1
print((ans*k)%m)

Solution (Python):
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())
    a -= 1
    b -= 1
    e[a].append(b)
    e[b].append(a)

col = [-1 for i in range(N)]
col[0] = 0
MOD = 10 ** 9 + 7


def dfs(i, ans, depth):
    
    
    if depth == 1:
        num = K - 1
    else:
        num = K - 2
    for v in e[i]:
        if col[v] == -1:
            col[v] = 0
            ans = (ans * num) % MOD
            num -= 1
            ans = dfs(v, ans, depth+1)

    return ans


print(dfs(0, K, 1))

Solution (Python):
N, K = map(int, input().split())
MOD = 10**9+7
edge = [[] for i in range(N)]
for i in range(N-1):
    a, b = map(lambda x:int(x)-1, input().split()) 
    edge[a].append(b)
    edge[b].append(a)

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

visit = [False]*N

def dfs(v):
    Stack = [v]
    visit[v] = True
    ans = K
    while Stack:
        v = Stack.pop()
        if v == 0:
            color = K-1
            ans *= P(color, len(edge[v]))
            ans %= MOD
        else:
            color = K-2
            child = 0
            for i in edge[v]:
                if not visit[i]:
                    child += 1
            ans *= P(color, child)
            ans %= MOD
        for i in edge[v]:
            if not visit[i]:
                visit[i] = True
                Stack.append(i)
    return ans

print(dfs(0))

Solution (Python):

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

mod=10**9+7

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

abc=[False for _ in range(n)]

abc[0]=True
c=0
ans=k
t=[] 

for i in range(len(path[0])):
	child=path[0][i]
	if abc[child]:
		continue
	ans=ans*(k-1-c)%mod
	c+=1
	abc[child]=True
	t.append(child)
while len(t)>0:
	a=t.pop()
	c=0
	for i in range(len(path[a])):
		child=path[a][i]
		if abc[child]:
			continue
		ans=ans*(k-2-c)%mod
		c+=1
		abc[child]=True
		t.append(child)
print(ans%mod)

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

AB = []
for _ in range(1, N):
    a, b = map(int, input().split())
    AB.append((a, b))
    
if N == 1:
    print(K)
else:
    
    graph = {}
    for a,b in AB:
        if not a in graph:
            graph[a] = {}
        if not b in graph:
            graph[b] = {}
        graph[a][b] = 1
        graph[b][a] = 1


    

    collors = [None] * (N+1)
    from collections import deque
    q = deque([(K, 1)]) 
    while q:
        col_num, v = q.popleft()
        if collors[v] == None:
            collors[v] = col_num

            if col_num == K:
                rest_col = K-1
            else:
                rest_col = K-2

            for v in graph[v]:
                if collors[v] == None:
                    q.appendleft((rest_col, v))
                    rest_col -= 1
    

    MOD = 10**9+7

    ans = 1
    for i in collors[1:]:
        ans = ans * i % MOD
    print(ans)

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):
N,K=map(int,input().split())
mod=1000000007
path=[[] for i in range(N)]
for i in range(N-1):
  a,b=map(int,input().split())
  a=a-1
  b=b-1
  path[a].append(b)
  path[b].append(a)

  
abc=[False for i in range(N)] 
 
abc[0]=True
cnt=0
ans=K%mod
nx=[]
for i in range(len(path[0])):
  child=path[0][i]
  if abc[child]:
    continue
  ans=ans*(K-1-cnt)
  ans=ans%mod
  cnt=cnt+1
  abc[child]=True
  nx.append(child)
while len(nx)>0:
  a=nx.pop()
  cnt=0
  for i in range(len(path[a])):
    child=path[a][i]
    if abc[child]:
      continue
    ans=ans*(K-2-cnt)
    ans=ans%mod
    cnt=cnt+1
    abc[child]=True
    nx.append(child)
      
print(ans%mod)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 5 + 5)

MOD = 10 ** 9 + 7


def dfs(current_node, parent_node, num_colors, graph):
    score = 1
    unavailable_colors = 0 if parent_node == -1 else 1
    for child_node in graph[current_node]:
        if child_node == parent_node:
            continue

        unavailable_colors += 1
        score = score * (num_colors - unavailable_colors) % MOD
        score = score * dfs(child_node, current_node, num_colors, graph) % MOD

    return score % MOD


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

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

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

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

    mod = 10 ** 9 + 7

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

    li = [-1] * n
    li[0] = k
    ans = 1
    stack = [0]

    while stack:
        label = stack.pop(-1)
        count = 1
        li2 = []
        for i in roots[label]:
            if li[i] == -1:
                stack.append(i)
                li2.append(i)
            else:
                count += 1
        for i in li2:
            li[i] = k - count
            count += 1

    for i in li:
        ans *= max(i,0)
        ans %= mod

    print(ans)

if __name__ == '__main__':
    main()

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

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

mod = 10 ** 9 + 7

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

li = [-1] * n
li[0] = k
ans = 1
stack = [0]

while stack:
    label = stack.pop(-1)
    count = 1
    li2 = []
    for i in roots[label]:
        if li[i] == -1:
            stack.append(i)
            li2.append(i)
        else:
            count += 1
    for i in li2:
        li[i] = k - count
        count += 1

for i in li:
    ans *= max(i,0)
    ans %= mod

print(ans)

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

def neighbor(N, edges):
    neighbor_list = [[] for _ in range(N)]
    for a, b in edges:
        neighbor_list[a-1] += [b-1]
        neighbor_list[b-1] += [a-1]
        
    return neighbor_list


def paint(K, nlist, now_num, from_num, case_num):
        mod = 1000000007
        if  from_num == -1:
            can_use_color = K - 1
        else:
            can_use_color = K - 2
        
        if len(nlist[now_num]) - 1 > can_use_color:
            return 0
        
        for child in nlist[now_num]:
            if child == from_num:
                continue
            else:
                case_num *= can_use_color
                can_use_color -= 1
                case_num %= mod
        
        for child in nlist[now_num]:
            if child == from_num:
                continue
            else:
                case_num = paint(K, nlist, child, now_num, case_num)
        return case_num%mod
            

if __name__ == '__main__':
    N, K = map(int, input().split())
    edges = [None]*(N-1)
    
    for i in range(N-1):
        edges[i] = list(map(int, input().split()))
    
    nlist = neighbor(N, edges)


    print(paint(K, nlist, 0, -1, K))

Solution (Python):
from itertools import groupby

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

num_of_perms = [1] * (K-1)
for i in range(1, K-1):
    num_of_perms[i] = num_of_perms[i-1] * ((K - 2) - i + 1) % 1000000007

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

if N == 1:
    res = K
else:
    res = K * (K-1)
    res %= 1000000007
    for g in groupby(sorted(Es)):
        c = len(list(g[1]))
        if c > K-1:
            res = 0
            break
        res *= num_of_perms[c-1]
        res %= 1000000007

print(res)

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

trees = {}
for _ in range(N-1):
    a, b = list(map(int, input().split()))
    if a not in trees.keys():
        trees[a] = set()
    if b not in trees.keys():
        trees[b] = set()
    trees[a].add(b)
    trees[b].add(a)

ans = K
if N > 1:
    memo = {1}
    targets = {1}
    while targets:
        next_targets = set()
        for target in targets:
            if target == 1:
                base = K-1
            else:
                base = K-2
            i = 0
            for child in trees[target]:
                if child not in memo:
                    memo.add(child)
                    ans = (ans*(base-i)) % (10**9+7)
                    next_targets.add(child)
                    i += 1
        targets = next_targets
print(ans)

Solution (Python):
def bfs(k):
    p=k
    level={1:1}
    frontier=[1]
    while frontier:
        next=[]
        for u in frontier:
            if u==1:
                l=k-1
            else:
                l=k-2
            i=0
            for v in adj[u]:
                if v not in level:
                    level[v]=1
                    p=(p*(l-i))%(10**9+7)
                    i+=1
                    next.append(v)
        frontier=next
    return p
n,k=map(int,input().split())
adj={}
for i in range(n-1):
    a,b=map(int,input().split())
    if a not in adj:
        adj[a]=[b]
    else:
        adj[a].append(b)
    if b not in adj:
        adj[b]=[a]
    else:
        adj[b].append(a)
if n==1:
  print(k)
else:
  print(bfs(k))

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




class FactMod():
    '''
    modの値が素数の時のfactと組み合わせを求める
    フェルマーの小定理を用いているため、modが素数以外の時は使えない
    '''

    def __init__(self, n, mod):
        '''
        コンストラクタ
        f:nまでの i!の値を　配列に入れる
        inv: (i!)^-1　の値を配列に入れる
        '''
        self.mod = mod
        self.f = [1]*(n+1)
        for i in range(1, n+1):
            self.f[i] = self.f[i-1]*i % mod

        self.inv = [pow(self.f[-1], mod-2, mod)]
        for i in range(1, n+1)[::-1]:
            self.inv.append(self.inv[-1]*i % mod)
        self.inv.reverse()

    def perm(self, a, b):
        if a < b or a < 0 or b < 0:
            return 0
        ret = self.f[a]*self.inv[a-b]
        ret %= self.mod
        return ret


MOD = 10**9+7
N, K = map(int, input().split())
edges = [list(map(lambda x:int(x)-1, input().split())) for _ in range(N-1)]
adj = [[] for _ in range(N)]

F = FactMod(K+1, MOD)

for a, b in edges:
    adj[a].append(b)
    adj[b].append(a)


Q = []
for a in adj[0]:
    Q.append((a, 0))
ans = F.perm(K, len(adj[0])+1)
ans %= MOD

while Q:
    current, prev = Q.pop()
    child = len(adj[current])-1
    ret = F.perm(K-2, child)
    ans *= ret
    ans %= MOD
    for a in adj[current]:
        if a == prev:
            continue
        else:
            Q.append((a, current))
print(ans)

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




class FactMod():
    '''
    modの値が素数の時のfactと組み合わせを求める
    フェルマーの小定理を用いているため、modが素数以外の時は使えない
    '''

    def __init__(self, n, mod):
        '''
        コンストラクタ
        f:nまでの i!の値を　配列に入れる
        inv: (i!)^-1　の値を配列に入れる
        '''
        self.mod = mod
        self.f = [1]*(n+1)
        for i in range(1, n+1):
            self.f[i] = self.f[i-1]*i % mod

        self.inv = [pow(self.f[-1], mod-2, mod)]
        for i in range(1, n+1)[::-1]:
            self.inv.append(self.inv[-1]*i % mod)
        self.inv.reverse()

    def perm(self, a, b):
        if a < b or a < 0 or b < 0:
            return 0
        ret = self.f[a]*self.inv[a-b]
        ret %= self.mod
        return ret


MOD = 10**9+7
N, K = map(int, input().split())
edges = [list(map(lambda x:int(x)-1, input().split())) for _ in range(N-1)]
adj = [[] for _ in range(N)]

F = FactMod(K+1, MOD)

for a, b in edges:
    adj[a].append(b)
    adj[b].append(a)


Q = []
for a in adj[0]:
    Q.append((a, 0))
ans = F.perm(K, len(adj[0])+1)
ans %= MOD

while Q:
    current, prev = Q.pop()
    child = len(adj[current])-1
    ret = F.perm(K-2, child)
    ans *= ret
    ans %= MOD
    for a in adj[current]:
        if a == prev:
            continue
        else:
            Q.append((a, current))
print(ans)

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

_input = [i for i in open(0).read().split('\n') if i]
n, k = [int(i) for i in _input[0].split()]
edge = tuple([tuple([int(p) for p in i.split()]) for i in _input[1:n]])

factorial = [0] * (k + 1)
inverse = [0] * (k + 1)
MOD = 1000000007


def mod_pow1(n, k, mod):
    a = 1
    while k:
        if (k & 1) == 1:
            a = (a * n) % mod
        n = (n * n) % mod
        k >>= 1
    return a


def mod_pow2(n, k, mod):
    if k == 0:
        return 1
    if k % 2 == 0:
        a = mod_pow2(n, k // 2, mod)
        return (a * a) % mod
    else:
        return (n * mod_pow2(n, k - 1, mod)) % mod



mod_pow = pow

def mod_factorial_inverse(k, mod):
    factorial[0] = 1
    inverse[0] = 1

    
    for i in range(1, k + 1):
        factorial[i] = ((i * factorial[i - 1]) % mod) 
        inverse[i] = mod_pow(factorial[i], mod - 2, mod) 
 
total = 1

if not edge:
    print(k)
else:
    all_edge = tuple([[] for _ in range(n + 1)])
    for e in edge:
        all_edge[e[0]].append(e[1])
        all_edge[e[1]].append(e[0])
    all_edge = [set(v) for v in all_edge]

    if [v for v in all_edge if len(v) >= k]:
        print(0)
    else:
        mod_factorial_inverse(k, MOD)

        root = edge[0]
        total = (factorial[k] * inverse[k - len(all_edge[root[0]]) - 1]) % MOD

        def dfs(current, from_):
            global total
            child = all_edge[current]
            if len(child) - 1 > 0:
                total = (total * factorial[k - 2] * inverse[k - 2 - (len(child) - 1)]) % MOD
            for c in child:
                if c != from_:
                    dfs(c, current)
        for c in all_edge[root[0]]:
            dfs(c, root[0])
        print(total)

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

_input = [i for i in open(0).read().split('\n') if i]
n, k = [int(i) for i in _input[0].split()]
edge = tuple([tuple([int(p) for p in i.split()]) for i in _input[1:n]])

factorial = [0] * (k + 1)
inverse = [0] * (k + 1)
MOD = 1000000007


def mod_pow1(n, k, mod):
    a = 1
    while k:
        if (k & 1) == 1:
            a = (a * n) % mod
        n = (n * n) % mod
        k >>= 1
    return a


def mod_pow2(n, k, mod):
    if k == 0:
        return 1
    if k % 2 == 0:
        a = mod_pow2(n, k // 2, mod)
        return (a * a) % mod
    else:
        return (n * mod_pow2(n, k - 1, mod)) % mod



mod_pow = pow

def mod_factorial_inverse(k, mod):
    factorial[0] = 1
    inverse[0] = 1

    
    for i in range(1, k + 1):
        factorial[i] = ((i * factorial[i - 1]) % mod) 
        inverse[i] = mod_pow(factorial[i], mod - 2, mod) 
 
total = 1

if not edge:
    print(k)
else:
    all_edge = tuple([[] for _ in range(n + 1)])
    for e in edge:
        all_edge[e[0]].append(e[1])
        all_edge[e[1]].append(e[0])
    all_edge = [set(v) for v in all_edge]

    if [v for v in all_edge if len(v) >= k]:
        print(0)
    else:
        mod_factorial_inverse(k, MOD)

        root = edge[0]
        total = (factorial[k] * inverse[k - len(all_edge[root[0]]) - 1]) % MOD

        def dfs(current, from_):
            global total
            child = all_edge[current]
            if len(child) - 1 > 0:
                total = (total * factorial[k - 2] * inverse[k - 2 - (len(child) - 1)]) % MOD
            for c in child:
                if c != from_:
                    dfs(c, current)
        for c in all_edge[root[0]]:
            dfs(c, root[0])
        print(total)