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

from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline())[:-1]
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)]

sys.setrecursionlimit(1000000)
mod = 1000000007


def A():
    n,a,b = LI()
    print(min(a*n,b))
    return


def B():
    n,d = LI()
    x = LIR(n)
    f = defaultdict(lambda : 0)
    for i in range(1000000):
        f[i*i] = 1
    ans = 0
    for i in range(n):
        for j in range(i+1,n):
            s = 0
            for k in range(d):
                s += (x[i][k]-x[j][k])**2
            if f[s]:
                ans += 1
    print(ans)
    return


def C():
    l,r = LI()
    if r-l > 2019:
        print(0)
        quit()
    ans = float("inf")
    for i in range(l,r+1):
        for j in range(i+1,r+1):
            if i*j%2019 < ans:
                ans = i*j%2019
    print(ans)
    return


def D():
    n = I()
    a = LI()
    for i in range(n):
        a[i] *= 2
    x = a[0]
    for i in range(1,n):
        if i%2:
            x -= a[i]
        else:
            x += a[i]
    b = [x//2]
    for i in range(n-1):
        b.append(abs(b[-1]-a[i]))
    print(*b)
    return


def E():
    n,k = LI()
    v = [[] for i in range(n)]
    for i in range(n-1):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
    if k == 1:
        if n == 1:
            print(1)
            quit()
        else:
            print(0)
            quit()
    if k == 2:
        print(2)
        quit()
    d = [0]*n
    v.append([])
    v.append([])
    q = deque([0])
    bfs = [1]*n
    bfs[0] = 0
    f = [0]*n
    while q:
        x= q.popleft()
        for y in v[x]:
            if bfs[y]:
                bfs[y] = 0
                q.append(y)
    ans = 1
    q = deque([0])
    dp = [None]*n
    dp[0] = k
    bfs = [1]*n
    bfs[0] = 0
    while q:
        x = q.popleft()
        m = len(v[x])
        for y in v[x]:
            if bfs[y]:
                bfs[y] = 0
                dp[y] = k-m
                m -= 1
                q.append(y)
    for i in dp:
        ans *= i
        ans %= mod
    print(ans)
    return


def F():
    n,q = LI()
    v = [[] for i in range(n)]
    for i in range(n-1):
        a,b,c,d = LI()
        a -= 1
        b -= 1
        c -= 1
        v[a].append((b,c,d))
        v[b].append((a,c,d))

    return



if __name__ == "__main__":
    E()

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

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

counted = [0]* (N+1) 

adjucent_dict = {}
for a,b in AB:
  adjucent_dict.setdefault(a, set()).add(b)
  adjucent_dict.setdefault(b, set()).add(a)
  
from collections import deque

dq = deque([])

for i in range(1,N+1):
  if len(adjucent_dict[i])==1:
    dq.append(i)
    


ans = K
while dq:
  v = dq.popleft()
  
  parent = adjucent_dict[v].pop() 
  adjucent_dict[parent].remove(v)
  
  ans *= max(0, K - (len(adjucent_dict[parent])+1))
  ans %= MOD
  
  if len(adjucent_dict[parent])==1:
    dq.append(parent)
  if len(adjucent_dict[parent])==0:
    break
  
print(ans)

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

n, k = [int(i) for i in input().split()]
A = [[int(i) for i in input().split()] for j in range(n - 1)]
p = 10 ** 9 + 7

E = [[] for i in range(n + 1)]

for a, b in A:
    E[a].append(b)
    E[b].append(a)

visited = [False] * (n + 1)

def dfs(i, f, s):
    if visited[i]:
        return 1
    b = f + s
    visited[i] = True
    
    res = k - b
    s = f
    f = 1
    for v in E[i]:
        if visited[v]:
            continue
        res *= dfs(v, f, s)
        res %= p
        s += 1

    return res if res > 0 else 0

print(dfs(1, 0, 0) % p)

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

nl = lambda: list(map(int, input().split()))
sl = lambda: input().split()
n = lambda: int(input())
s = lambda: input()

N, K = nl()

from collections import defaultdict
edges = defaultdict(set)
for i in range(N-1):
    a, b = nl()
    edges[a].add(b)
    edges[b].add(a)


done = [False] * (N+1)
done[1] = True

def find(i, cands, prev):
    res = cands

    count = 0
    if prev:
        count += 1
    for edge in edges[i]:
        if done[edge]:
            continue
        count += 1
        done[edge] = True
        res *= find(edge, K - count, True)
        res %= 1000000007
    return res


print(find(1, K, False))

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
N, K = map(int, input().split())
mod = 10**9 + 7
G = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
def p(n, k):
    x = 1
    for i in range(k):
        x *= n - i
        x %= mod
    return x
def f(x, par):
    L = len(G[x])
    if x == par:
        if L <= K-1:
            ans = K*p(K-1,L) % mod
        else:
            return 0
    elif x != par:
        if L-1 <= K-2:
            ans = p(K-2,L-1)
        else:
            return 0
    for i in G[x]:
        if i != par:
            ans *= f(i, x)
            ans %= mod
    return ans
print(f(0, 0))

Solution (Python):
import sys
sys.setrecursionlimit(100100)
from collections import deque
def factorials(M):
    INF=int(1e9+7)
    fac=[0]*(M+1)
    finv=[0]*(M+1)
    inv=[0]*(M+1)
    fac[0]=fac[1]=1
    finv[0]=finv[1]=1
    inv[1]=1
    for i in range(2,M+1):
        fac[i]=(fac[i-1]*i)%INF
        inv[i]=INF-(inv[INF%i]*(INF//i))%INF
        finv[i]=finv[i-1]*inv[i]%INF
    return fac,finv

N,K=map(int,input().split())
fac,finv=factorials(max(N,K))
def nCr(n,r):
    INF=int(1e9+7)
    if n<r or r<0 or n<0 :
        return 0
    return fac[n]*(finv[r]*finv[n-r]%INF)%INF
A=[0]*N
G=[[] 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
    A[a]+=1
    A[b]+=1
    G[a].append(b)
    G[b].append(a)
ans=K
can=K
grand=0
gpare=-1
stack=deque([[0,gpare]])
while(stack):
    pare,gpare=stack.pop()
    childs=G[pare]
    ans*=nCr(K-1-grand,len(childs)-grand)*fac[len(childs)-grand]
    ans%=MOD
    grand=1
    for i in childs:
        if i==gpare:
            continue
        if A[i]-1==0:
            continue
        stack.append([i,pare])
print(ans)

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

n, k = [int(i) for i in input().split()]
A = [[int(i) for i in input().split()] for j in range(n - 1)]
p = 10 ** 9 + 7

E = [[] for i in range(n + 1)]

for a, b in A:
    E[a].append(b)
    E[b].append(a)

visited = [False] * (n + 1)

def dfs(i, f, s):
    if visited[i]:
        return 1
    b = f + s
    visited[i] = True
    
    res = k - b
    s = f
    f = 1
    for v in E[i]:
        if visited[v]:
            continue
        res *= dfs(v, f, s)
        res %= p
        s += 1

    return res if res > 0 else 0

print(dfs(1, 0, 0) % p)

Solution (Python):
n,k = map(int,input().split())


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

for i in range(n - 1):
	A,B = map(int,input().split())
	
	
	c[A - 1].append(B - 1)
	c[B - 1].append(A - 1)

pat = k
pat_arr = [0 for _ in range(n)]
pat_arr[0] = k
queue = [0]



while(queue):
	pos = queue.pop(0)
	num = k-2
	if(pos == 0):num += 1
	
	for i in c[pos]:
		if(pat_arr[i] != 0):continue
		queue.append(i)
		pat_arr[i] = num
		pat *= num
		pat %= 1000000007
		num -= 1
		
		
print(pat % 1000000007)

Solution (Python):


MOD = 10**9 + 7


fact = [1]

k = 1
for i in range(10**5):
    k = k*(i+1)%MOD
    fact.append(k)


def getModInv(a, b):
    return 1 if (a == 1) else int((1-b*getModInv(b%a, a))/a%b)


def modPerm(n, m):
    if m > n:
        return 0

    if m == 0:
        return 1

    return fact[n]*getModInv(fact[n-m], MOD)%MOD



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

    subNodes = [set() for _ in range(N+1)]
    for a, b in AB:
        subNodes[a].add(b)
        subNodes[b].add(a)

    G = [set() for _ in range(N+1)]
    Q = set([1])
    
    while len(Q) > 0:
        q = Q.pop()
        for subNode in subNodes[q]:
            if len(G[subNode]) == 0:
                G[q].add(subNode)
                Q.add(subNode)

    p = K*modPerm(K-1, len(G[1]))%MOD

    for subNodes in G[2:]:
        p = p*modPerm(K-2, len(subNodes))%MOD

    print(p)

        

if __name__ == '__main__':
    main()

Solution (Python):
import os
import sys
from collections import deque
from functools import lru_cache, reduce
from operator import mul

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 1000000007


def get_factorials(max, mod=None):
    """
    階乗 0!, 1!, 2!, ..., max!
    :param int max:
    :param int mod:
    :return:
    """
    ret = [1]
    n = 1
    if mod:
        for i in range(1, max + 1):
            n *= i
            n %= mod
            ret.append(n)
    else:
        for i in range(1, max + 1):
            n *= i
            ret.append(n)
    return ret


def mod_invs(max, mod):
    """
    :param max:
    :param mod:
    :return:
    """
    invs = [1] * (max + 1)
    for x in range(2, max + 1):
        invs[x] = (-(mod // x) * invs[mod % x]) % mod
    return invs


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

factorials = get_factorials(max=K, mod=MOD)
invs = mod_invs(K, MOD)


def mod_inv(a, mod):
    """
    a の逆元
    :param int a:
    :param int mod:
    :return:
    """
    return pow(a, mod - 2, mod)


@lru_cache(maxsize=None)
def npr(n, r, mod=None):
    """
    :param int n:
    :param int r:
    :param int mod: 3 以上の素数であること
    :rtype: int
    """
    if n < r:
        return 0

    
    
    if r == 0:
        return 1

    return factorials[n] * mod_inv(factorials[n-r], mod) % MOD


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

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

leaf = None
for i in range(N):
    if len(graph[i]) == 1:
        leaf = i
        break

v = graph[leaf][0]
ans = npr(K, len(graph[v]) + 1, MOD)
seen = [False] * (N + 1)
seen[v] = True
que = deque()
for u in graph[v]:
    que.append(u)
    seen[u] = True

while que:
    v = que.popleft()
    seen[v] = True
    if len(graph[v]) == 1:
        continue
    ans *= npr(K - 2, len(graph[v]) - 1, MOD)
    ans %= MOD
    for u in graph[v]:
        if not seen[u]:
            que.append(u)

print(ans)

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

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

N, K = MAP()

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

color = list(range(K))

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

ans = 1
q = deque()
q.append((None, 0))
color = [K]*N

while q:
	from_node, to_node = q.popleft()
	if from_node == None:
		ans *= K
		
	else:
		ans = (ans * color[from_node])%mod
		
	if from_node != None:
		color[to_node] = color[from_node]
		color[from_node] -= 1
	if color[to_node] >= K-1:
		color[to_node] -= 1
	else:
		color[to_node] = K-2
	for node in graph[to_node]:
		if from_node == None:
			q.append((to_node, node))
		else:
			if node != from_node:
				q.append((to_node, node))
	
print(ans)

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

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

l = [0 for i in range(n)]
ll = [[]for i in range(n)]

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

if n==1:
    print(k)
    exit()

q = max(l)
if k<q+1:
    print(0)
    exit()

f = [1,1]
for i in range(2,k+1):
    f.append(f[-1]*i%m)

g = [1]
for i in range(k):
    g.append(pow(f[i+1],m-2,m))


ans = k

ans *= f[k-1]*g[k-1-l[0]]
ans %= m

visited = [0]*n
visited[0]==1
for x in ll[0]:
    visited[x]==1

for i in range(1,n):
    if visited[i] ==0:
        ans *= f[k-2]*g[k-1-l[i]]
        ans %= m
        for x in ll[i]:
            visited[x]==1

print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(100000)
n,k=map(int,input().split())
ans=k
t=[set()for i in range(n)]
dp=[k]+[0]*(n-1)
for i in range(n-1):
  a,b=map(int,input().split())
  t[a-1].add(b)
  t[b-1].add(a)
no=1
w=k
b=True
def a(noo):
  global ans
  w=k
  for i in t[noo-1]:
    t[i-1].discard(noo)
    if w==0:print(0);exit()
    dp[i-1]=w-2;ans=(ans*(w-2))%(10**9+7)
    w-=1
    a(i)
for i in t[no-1]:
  t[i-1].discard(no)
  w-=1
  dp[i-1]=w;ans=(ans*w)%(10**9+7)
  a(i)
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(100000)
n,k = map(int,input().split())
x = [[] for _ in range(n+1)]
for _ in range(n-1):
  a,b = map(int,input().split())
  x[a].append(b)
  x[b].append(a)
ans = k
def search(i):
  l = len(x[i])
  if l == 0:
    return
  global ans
  for j in range(l):
    ans = (ans*(k-2-j))%1000000007
  for child in x[i]:
    x[child].remove(i)
    search(child)
l1 = len(x[1])
for j in range(l1):
  ans = (ans*(k-1-j))%1000000007
for child1 in x[1]:
  x[child1].remove(1)
  search(child1)
print(ans)

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


def solve():
    N, K = map(int, input().split())
    AB = [[] for _ in range(N + 1)]
    for _ in range(N - 1):
        a, b = map(int, input().split())
        AB[a].append(b)
        AB[b].append(a)

    
    
    print(dfs(AB, 1, 0, 0, 1, K, 0) % (10 ** 9 + 7))


def dfs(hen, cho, kai, ko, tag, K, oya):
    tag *= K - (ko - 1 if ko > 0 else 0) - (2 if kai >= 2 else kai)
    next_ko = hen[cho].copy()
    if oya != 0:
        next_ko.remove(oya)
    for i in range(len(next_ko)):
        tag = dfs(hen, next_ko[i], kai + 1, i + 1, tag, K, cho)
    return tag % (10 ** 9 + 7)


if __name__ == '__main__':
    solve()

Solution (Python):
import sys
sys.setrecursionlimit(100000)
n,k = map(int,input().split())
x = [[] for _ in range(n+1)]
for _ in range(n-1):
  a,b = map(int,input().split())
  x[a].append(b)
  x[b].append(a)
ans = k
def search(i):
  l = len(x[i])
  if l == 0:
    return
  global ans
  for j in range(l):
    ans = (ans*(k-2-j))%1000000007
  for child in x[i]:
    x[child].remove(i)
    search(child)
l1 = len(x[1])
for j in range(l1):
  ans = (ans*(k-1-j))%1000000007
for child1 in x[1]:
  x[child1].remove(1)
  search(child1)
print(ans)

Solution (Python):


import itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect
from heapq import heappush, heappop

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

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

    
    patterns = [-1] * n
    
    stack = deque()
    patterns[0] = k

    rest = k - 1
    for neighbor in edges[0]:
        patterns[neighbor] = max(0, rest)
        rest -= 1
        stack.append(neighbor)

    while len(stack) > 0:
        node = stack.pop()

        rest = k - 2
        for neighbor in edges[node]:
            if patterns[neighbor] == -1:
                patterns[neighbor] = max(0, rest)
                rest -= 1
                stack.append(neighbor)

    ans = 1
    for p in patterns:
        ans = ans * p % mod

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(1000000000)
mod = 10**9+7
N, K = map(int, input().split())
edge = [[] for _ in range(N)]
flag = [False]*N
flag[0] = True
for i in range(N-1):
    a, b = map(int, input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
P = [1]*(K+10)
T = [1]*(K+10)
for i in range(1, K+10):
    P[i] = (P[i-1]*(K-i))%mod
    T[i] = T[i-1]*(K-i-1)%mod
def count(x):
    flag[x]=True
    res = 1
    l = len(edge[x])-1
        
    for e in edge[x]:
        if flag[e]:
            continue
        res*=count(e)
    if x==0:
        if l+1> K-1:
            return 0
        return res*K*P[l+1]%mod
    if l>K-2:
        return 0
    return res*T[l]%mod
print(count(0))

Solution (Python):
from collections import deque


def solve(N, K, ABs):
    if N == 1:
        return K

    Ds = [-1 for _ in range(N + 1)]
    Ws = {i: [] for i in range(N + 1)}
    for a, b in ABs:
        Ws[a].append(b)
        Ws[b].append(a)

    for i in range(1, N + 1):
        if Ds[i] == -1:
            Ds[i] = K

            if Ws[i]:
                s = Ws[i][0]
                Ds[s] = K - 1

                queue = deque()
                queue.append(i)
                queue.append(s)

                while queue:
                    s = queue.popleft()
                    k = K - 2
                    for w in Ws[s]:
                        if Ds[w] == -1:
                            Ds[w] = k
                            k -= 1
                            queue.append(w)

    ans = 1
    for i in range(1, N + 1):
        if Ds[i] <= 0:
            return 0
        ans *= Ds[i]
        ans %= 1000000007
    return ans % 1000000007

if __name__ == "__main__":
    N, K = tuple(map(int, input().split(" ")))
    ABs = [tuple(map(int, input().split(" "))) for _ in range(N - 1)]
    print(solve(N, K, ABs))

Solution (Python):
def inpl(): return map(int, input().split())
from itertools import accumulate
from bisect import bisect, bisect_left
from collections import Counter, deque
from functools import reduce
from itertools import accumulate
from operator import itemgetter, xor

from sys import setrecursionlimit
setrecursionlimit(10**9)
 
import sys

from collections import Counter
def inpl(): return list(map(int, input().split()))

MOD = 10**9 + 7
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod


size = 2 * 10**5
g1, g2, inverse = [0]*size, [0]*size, [0]*size
 
g1[:2] = [1, 1] 
g2[:2] = [1, 1] 
inverse[:2] = [0, 1] 
 
for i in range(2, size):
    g1[i] =  ( g1[i-1] * i ) % MOD 
    inverse[i] = (-inverse[MOD % i] * (MOD//i) ) % MOD 
    g2[i] =  (g2[i-1] * inverse[i]) % MOD



N, K = inpl()
G = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = inpl()
    G[a-1].append(b-1)
    G[b-1].append(a-1)
C = [0]*N
P = [0]*N
searched = [0]*N
searched[0] = 1

"""
def count(p):
    global C, searched
    cnt = 0
    for q in G[p]:
        if not searched[q]:
            P[q] = p
            searched[q] = 1
            cnt += 1
            count(q)
    C[p] = cnt
count(0)"""

Q = deque([0])
while Q:
    p = Q.popleft()
    for q in G[p]:
        if not searched[q]:
            P[q] = p
            searched[q] = 1
            C[p] += 1
            Q.append(q)


ans = K * cmb(K-1, C[0], MOD) * g1[C[0]] % MOD
for i in range(1, N):
    if C[i] == 0:
        continue
    ans = ans * cmb(K-2, C[i], MOD) * g1[C[i]] % MOD

print(ans%MOD)

Solution (Python):
from collections import defaultdict
import Queue

def npk(n,k,mod):
	temp = 1
	for i in xrange(n,n-k,-1):
		temp *= i
		temp %= mod
	return temp

mod = 10**9+7
n,k = map(int,raw_input().split())
g = defaultdict(list)
for i in xrange(n-1):
	a,b = map(int,raw_input().split())
	g[a].append(b)
	g[b].append(a)


res = k
q = Queue.Queue()
q.put((1,0))
while not q.empty():
	node = q.get()
	children = g[node[0]]
	c = len(children)
	if node[0] == 1:
		res *= npk(k-1,c,mod)
	else:
		res *= npk(k-2,c-1,mod)
	res %= mod
	for x in children:
		if x != node[1]:
			q.put((x,node[0]))
print res

Solution (Python):
n, m = [int(i) for i in input().split()]


G = [[] for i in range(n + 1)]
C = [m for i in range(n + 1)]
for i in range(n - 1):
    x, y = [int(i) for i in input().split()]
    
    G[x].append(y)
    G[y].append(x)

ans = 1
def dfs(s):
    global ans, C, G
    stack = [s]
    while len(stack):
        u = stack[len(stack) - 1]
        stack.pop()
        ans *= C[u]
        ans %= 1000000007
        
        tot = 1
        if u != 1:
            tot += 1
        for v in G[u]:
            C[v] -= tot
            G[v].remove(u)
            stack.append(v)
            tot += 1

dfs(1)
print(ans)

Solution (Python):
MOD = 10**9 + 7
def permutation(n,k):
	ret = 1
	for i in range(n-k+1,n+1):
		ret *= i
	return ret

N,K = map(int,input().split())
edge = [[] for i in range(N)]
for i in range(N-1):
	a,b = map(int,input().split())
	edge[a-1].append(b-1)
	edge[b-1].append(a-1)
searched = [False for i in range(N)]
searched[0] = True
dp = [1 for i in range(N)]
dp[0] = K
search = [(0,0)]
while len(search) > 0:
	x = search.pop()
	d,n = x[0], x[1]
	colors = K - min(2, d+1)
	for n2 in edge[n]:
		if not searched[n2]:
			searched[n2] = True
			dp[n2] = colors
			colors -= 1
			search.append((d+1,n2))
ans = 1
for i in dp:
	ans = (ans * i) % MOD
print(ans)

Solution (Python):
M = 1000000007
n, k = map(int, input().split())

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

for i in range(n - 1):
    f, t = map(int, input().split())
    graph[f - 1].append(t - 1)
    graph[t - 1].append(f - 1)

visited = [False] * n

visited[0] = True
cnt = 0
ans = k
que = [0]
while que:
    node = que.pop()
    visited[node] = True
    node_cnt = 0
    for next_node in graph[node]:
        if not visited[next_node]:
            que.append(next_node)
            if cnt < 1:
                ans *= k - 1
                cnt += 1
                node_cnt -= 1
            else:
                ans *= (k - (2 + node_cnt))
                if ans > M:
                    ans %= M
            node_cnt += 1
print(ans % M)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
inpl = lambda: list(map(int,input().split()))
MOD = 10**9 + 7

N, K = inpl()
edges = [set() for _ in range(N)]
for _ in range(N-1):
    a, b = inpl()
    a -= 1
    b -= 1
    edges[a].add(b)
    edges[b].add(a)

def dfs(node, colors, root=True):
    if colors == 0:
        return 0
    prod = colors
    if root:
        next_colors = K - 1
    else:
        next_colors = K - 2
    for p in edges[node]:
        if next_colors <= 0:
            return 0
        edges[p].remove(node)
        prod = prod*dfs(p,next_colors,False) % MOD
        if prod == 0:
            return 0
        next_colors -= 1
    return prod

print(dfs(0,K))

Solution (Python):
from collections import deque

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

G = dict()
for i in range(1, N + 1):
    G[i] = dict()

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

root = 1
queue = deque([root])

depth = [N + 1] * (N + 1)
depth[root] = 0

c_list = [root]

while len(queue) > 0:

    p = queue.popleft()

    for q in G[p].keys():
        if depth[q] == N + 1:
            depth[q] = depth[p] + 1
            c_list.append(q)
            queue.append(q)


perm = [1]
for i in range(K - 2):
    perm.append((perm[-1] * (K - 2 - i)) % LARGE)


res = 1
for i in range(len(G[root].keys()) + 1):
    res = res * (K - i) % LARGE

for c in c_list[1:]:
    if len(G[c].keys()) >= K:
        res = 0
    else:
        res = res * perm[len(G[c].keys()) - 1] % LARGE

print(res)

Solution (Python):

import sys
sys.setrecursionlimit(100000)
from collections import deque
from collections import defaultdict
INF = float("inf")

MOD = 1000000007  


def solve(N: int, K: int, a: "List[int]", b: "List[int]"):
    
    edges = defaultdict(list)
    for from_, to_ in zip(a, b):
        edges[from_].append(to_)
        edges[to_].append(from_)

    
    flag = [False]*(N+1)

    def recur(n, preK, prepreK):
        count = 1
        count *= K-preK-prepreK
        count %= MOD
        flag[n] = True
        if edges[n] == 1:
            print(n, preK, prepreK, count)
            return count
        else:
            e = [ee for ee in edges[n] if flag[ee] is False]
            for i, to_ in enumerate(e):
                count *= recur(to_, 1, preK+i)
                count %= MOD
            return count

    print(recur(1, 0, 0) % MOD)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    K = int(next(tokens))  
    a = [int()] * (N-1)  
    b = [int()] * (N-1)  
    for i in range(N-1):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    solve(N, K, a, b)


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

MOD = int(1e9) + 7
MAX = int(2e5)


def div(a, b):
    return a * pow(b, MOD-2, MOD) % MOD


FACT = [1] * (MAX+1)
for i in range(1, MAX+1):
    FACT[i] = (i * FACT[i-1]) % MOD
INV = [1] * (MAX+1)
INV[MAX] = div(1, FACT[MAX])
for i in range(MAX, 0, -1):
    INV[i-1] = (INV[i] * i) % MOD


def main():
    N, K = map(int, input().split())
    adj = [set() for _ in range(N)]
    for _ in range(N-1):
        a, b = map(int, input().split())
        adj[a-1].add(b-1)
        adj[b-1].add(a-1)
    ans = 1
    q = deque()
    q.append((0, -1))
    while len(q):
        cur, prev = q.pop()
        if len(adj[cur]) + 1 > K:
            print(0)
            return
        if prev == -1:
            tmp = FACT[K] * INV[K - (len(adj[cur]) + 1)]
        else:
            tmp = FACT[K - 2] * INV[K - 2 - (len(adj[cur])-1)]
        ans = (ans * tmp) % MOD
        for nxt in adj[cur]:
            if nxt == prev:
                continue
            q.append((nxt, cur))
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys

inf = 10 ** 18
P = 10 ** 9 + 7

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

graph = [[] for _ in range(N)]
for i, (ai, bi) in enumerate(ab):
    graph[ai - 1].append(bi)
    graph[bi - 1].append(ai)

for i_root in range(1, N + 1):
    if len(graph[i_root - 1]) > 1: break

from collections import deque

cnts = [None] * N
cnts[i_root - 1] = K

q = deque([i_root])
while len(q) > 0:
    src = q.popleft()
    idx = 0
    for dst in graph[src - 1]:
        if cnts[dst - 1] == None:
            parents = 1 if src == i_root else 2
            cnt_tmp = K - parents - idx
            cnts[dst - 1] = cnt_tmp if cnt_tmp > 0 else 0
            
            q.append(dst)
            idx += 1




ans = 1



for cnt in cnts:
    ans = (ans * cnt) % P
    if cnt == 0: break

print(ans)

Solution (Python):
import collections
N,K=[int(_) for _ in input().split()]
AB=[[int(_) for _ in input().split()] for _ in range(N-1)]
mod=10**9+7
G=collections.defaultdict(set)
for a,b in AB:
    G[a].add(b)
    G[b].add(a)
count=collections.defaultdict(int)
for i in range(1,N+1):
    count[i]=len(G[i])-1
ans=collections.defaultdict(int)
for k,v in count.items():
    if k!=1:
        ans[v]+=1


fact=[0]*(N+1)
fact[0]=1
fact[1]=K-2
for i in range(2,N+1):
    fact[i]=fact[i-1]*(K-i-1)%mod

ret=K
for i in range(len(G[1])):
    ret*=(K-1-i)
ret%=mod
for k,v in ans.items():
    ret*=pow(fact[k],v,mod)
    ret%=mod
print(ret)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)


def main():
    n, k = map(int, input().split())
    MOD = 10 ** 9 + 7
    t = [{} for _ in range(n)]
    for _ in range(n-1):
        a, b = map(int, input().split())
        t[a-1][b-1] = 1
        t[b-1][a-1] = 1
    values = [1] * n

    def dfs(x):
        colors = k - 2
        for y in t[x]:
            del t[y][x]
            values[y] = colors
            colors -= 1
            dfs(y)

    values[0] = k
    colors = k - 1
    for x in t[0]:
        del t[x][0]
        values[x] = colors
        colors -= 1
        dfs(x)

    ans = 1
    for v in values:
        ans *= v
        ans %= MOD
    print(ans)


main()

Solution (Python):
INF=10**9+7
n,k=map(int,input().split())
graph=[[] for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
ans=1
check=[False]*n
import sys
sys.setrecursionlimit(10**6)
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):
from collections import deque
mod = 10**9+7
N,K = map(int,input().split())
e = [[] for _ in range(N)]
d = {}
for _ in range(N-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    e[a].append(b)
    e[b].append(a)
    d[(min(a,b),max(a,b))] = 0
ans = K
parents = deque([0])

n = [0]*N
while parents:
    p = parents.popleft()
    for c in e[p]:
        if d[(min(p,c),max(p,c))] == 0:
            d[(min(p,c),max(p,c))] = 1
            n[p] += 1
            n[c] += 1
            parents.append(c)
            ans *= K-n[p]
            ans %= mod

print(ans)

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

MOD = 10**9 + 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)

if n == 1:
    print(k)
else:
    visited = [False for i in range(n)]
    def dfs(v, npv, nppv):
        global visited
        ans = max(k - npv - nppv, 0)
        visited[v] = True
        i = 0
        for nv in e[v]:
            if visited[nv]:
                continue

            ans *= dfs(nv, 1, npv+i)
            ans = ans % MOD
            i += 1

        return ans

    for i in range(n):
        if len(e[i]) == 1:
            
            s = i
            break

    print(dfs(s, 0, 0))

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

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

T = [True]*N
T[0] = False
ans = K
for i in range(len(S[0])):
    T[S[0][i]] = False
    ans *= K-1-i
queue = deque(S[0])
while queue != deque([]):
    q = queue.popleft()
    hoge = 0
    for i in S[q]:
        if T[i]:
            T[i] = False
            queue.append(i)
            hoge += 1
    piyo = 1
    for i in range(hoge):
        piyo = (piyo * (K-2-i))%(10**9+7)
    ans = (ans*piyo)%(10**9+7)
print(ans)