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, 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
sys.setrecursionlimit(10 ** 9)



INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
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 = 10 ** 9 + 7


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


que = [0]
ans = k
visited = [0] * n
c_num = [0] * n
visited[0] = 1
while que:
    u = que.pop()
    for v in G[u]:
        if visited[v] == 0:
            if u == 0:
                ans = ans * (k - 1 - c_num[u]) % mod
            else:
                ans = ans * (k - 2 - c_num[u]) % mod
            c_num[u] += 1
            visited[v] = 1
            que += [v]


print(ans)

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


def perm(n, k):
    if k == 0:
        return 1
    return n * perm(n-1, k-1) % mod


n, k = map(int, input().split())
child = [0] * n

for _ in range(n-1):
    a, b = map(lambda x: int(x)-1, input().split())
    child[a] += 1
    child[b] += 1

ans = k
for i in range(n):
    if i == 0:
        color = k - 1
        num = child[i]
    else:
        color = k - 2
        num = child[i] - 1
    ans = ans * perm(color, num) % mod

print(ans)

Solution (Python):
import sys

mod=10**9+7
table=[1]*(10**5+100)
for i in range(2,10**5+100):
    table[i]=(table[i-1]*i)%mod
    

g1=[1,1]
g2=[1,1]
for i in range(2,10**5+100):
    num_1=g1[-1]*i%mod
    g1.append(num_1)
    g2.append(pow(num_1,mod-2,mod))  
def cmb(n,r,MOD):
    if n<r or n<=0:
        return 0
    else:
        return g1[n]*g2[r]*g2[n-r]%MOD
    

n,k=map(int,input().split())
data=[[] for i in range(n+1)]
for i in range(n-1):
    a,b=map(int,input().split())
    data[a].append(b)
    data[b].append(a)
if k==2:
    if n<=2:
        print(2)
    else:
        print(0)
    sys.exit()
if k==1:
    if n==1:
        print(1)
    else:
        print(0)
    sys.exit()
flag=[0]*(n+1)
ans=1
ans=cmb(k,len(data[1])+1,mod)*table[len(data[1])+1]%mod
que=data[1]
flag[1]=1
for u in data[1]:
    flag[u]=1
while que:
    h=[]
    for u in que:
        count=0
        for v in data[u]:
            if flag[v]==0:
                flag[v]=1
                h.append(v)
                count+=1
        ans=(ans*cmb(k-2,count,mod)*table[count])%mod
    que=h
print(ans)

Solution (Python):
from collections import deque

class Combination:
    def __init__(self, size, mod=10**9 + 7):
        self.size = size + 2
        self.mod = mod
        self.fact = [1, 1] + [0] * size
        self.factInv = [1, 1] + [0] * size
        self.inv = [0, 1] + [0] * size

        for i in range(2, self.size):
            self.fact[i] = self.fact[i - 1] * i % self.mod
            self.inv[i] = -self.inv[self.mod % i] * (self.mod // i) % self.mod
            self.factInv[i] = self.factInv[i - 1] * self.inv[i] % self.mod

    def npr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * self.factInv[n - r] % self.mod

    def ncr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * (self.factInv[r] * self.factInv[n - r] % self.mod) % self.mod

    def factN(self, n):
        if n < 0:
            return 0
        return self.fact[n]

N, K = map(int, input().split())
MOD = 10**9 + 7
edges = [[] for _ in range(N)]

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

comb = Combination(N + K + 100)

chCnt = [0] * N
que = deque([(0, -1)])
while que:
    now, pr = que.popleft()
    chCnt[now] = len(edges[now]) - 1
    for to in edges[now]:
        if to != pr:
            que.append((to, now))
chCnt[0] += 1

ans = K
que = deque([(0, -1)])
while que:
    now, pr = que.popleft()

    if pr == -1:
        ans *= comb.npr(K - 1, chCnt[now])
    else:
        ans *= comb.npr(K - 2, chCnt[now])

    ans %= MOD
    for to in edges[now]:
        if to != pr:
            que.append((to, now))

print(ans % MOD)

Solution (Python):
import sys
sys.setrecursionlimit(90000)
n,K=map(int,input().split())
visitedlist=[-1 for  i in range(n)]
kilist=[[] for i in range(n)]
anslist=[0 for i in range(n)]
searchedlist=[-1 for i in range(n)]
for i in range(n-1):
        a,b=map(int,input().split())
        kilist[a-1].append(b)
        kilist[b-1].append(a)
def search(P):
        searchedlist[P-1]=1
        visitedlist[P-1]=1
        flag=0
        for j in kilist[P-1]:
            if visitedlist[j-1]<0:
                visitedlist[j-1]=1
                flag+=1
                anslist[j-1]=anslist[P-1]+1
        else:
            pass

        if flag>0:    
            for k in kilist[P-1]:
                if searchedlist[k-1]==-1:
                    search(k)
def find_power(n):
    
    powlist=[0]*(n+1)
    powlist[0]=1
    powlist[1]=1
    for i in range(2,n+1):
        powlist[i]=powlist[i-1]*i%(10**9+7)
    return powlist
def find_inv_power(n):
    
    powlist=find_power(n)
    check=powlist[-1]
    first=1
    uselist=[0]*(n+1)
    secondlist=[0]*30
    secondlist[0]=check
    secondlist[1]=check**2
    for i in range(28):
        secondlist[i+2]=(secondlist[i+1]**2)%(10**9+7)
    a=format(10**9+5,"b")
    for j in range(30):
        if a[29-j]=="1":
            first=(first*secondlist[j])%(10**9+7)
    uselist[n]=first
    for i in range(n,0,-1):
        uselist[i-1]=(uselist[i]*i)%(10**9+7) 
    return uselist
search(1)
power=find_power(100000)
invpower=find_inv_power(100000)
distancelist=[(i+1,anslist[i]) for i in range(n)]
distancelist=sorted(distancelist,key=lambda x:x[1])
answer=1
for some in distancelist:
    if some[1]==0:
        answer*=K
        howmuch=len(kilist[some[0]-1])   
        if K-1<howmuch:
            answer=0
            break
        else:
            answer=answer*power[K-1]*invpower[K-1-howmuch]
            answer=answer%(10**9+7)        
    else:
        howmuch=len(kilist[some[0]-1])-1
        if howmuch==0:
            pass
        else:
            if K-2<howmuch:
                answer=0
                break
            else:
                answer=answer*power[K-2]*invpower[K-2-howmuch]
                answer=answer%(10**9+7)
print(answer)

Solution (Python):
import sys
sys.setrecursionlimit(100000)
n,K=map(int,input().split())
visitedlist=[-1 for  i in range(n)]
kilist=[[] for i in range(n)]
anslist=[0 for i in range(n)]
searchedlist=[-1 for i in range(n)]
for i in range(n-1):
        a,b=map(int,input().split())
        kilist[a-1].append(b)
        kilist[b-1].append(a)
def search(P):
        searchedlist[P-1]=1
        visitedlist[P-1]=1
        flag=0
        for j in kilist[P-1]:
            if visitedlist[j-1]<0:
                visitedlist[j-1]=1
                flag+=1
                anslist[j-1]=anslist[P-1]+1
        else:
            pass

        if flag>0:    
            for k in kilist[P-1]:
                if searchedlist[k-1]==-1:
                    search(k)
def find_power(n):
    
    powlist=[0]*(n+1)
    powlist[0]=1
    powlist[1]=1
    for i in range(2,n+1):
        powlist[i]=powlist[i-1]*i%(10**9+7)
    return powlist
def find_inv_power(n):
    
    powlist=find_power(n)
    check=powlist[-1]
    first=1
    uselist=[0]*(n+1)
    secondlist=[0]*30
    secondlist[0]=check
    secondlist[1]=check**2
    for i in range(28):
        secondlist[i+2]=(secondlist[i+1]**2)%(10**9+7)
    a=format(10**9+5,"b")
    for j in range(30):
        if a[29-j]=="1":
            first=(first*secondlist[j])%(10**9+7)
    uselist[n]=first
    for i in range(n,0,-1):
        uselist[i-1]=(uselist[i]*i)%(10**9+7) 
    return uselist
search(1)
power=find_power(100000)
invpower=find_inv_power(100000)
distancelist=[(i+1,anslist[i]) for i in range(n)]
distancelist=sorted(distancelist,key=lambda x:x[1])
answer=1
for some in distancelist:
    if some[1]==0:
        answer*=K
        howmuch=len(kilist[some[0]-1])   
        if K-1<howmuch:
            answer=0
            break
        else:
            answer=answer*power[K-1]*invpower[K-1-howmuch]
            answer=answer%(10**9+7)        
    else:
        howmuch=len(kilist[some[0]-1])-1
        if howmuch==0:
            pass
        else:
            if K-2<howmuch:
                answer=0
                break
            else:
                answer=answer*power[K-2]*invpower[K-2-howmuch]
                answer=answer%(10**9+7)
print(answer)

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):
import queue
n,k = map(int,input().split())

ab = [[] for j in range(n+1)]
mod = 10**9 + 7

for i in range(n-1):
    a,b = map(int,input().split())
    ab[a].append(b)
    ab[b].append(a)
    
check = [False] * (n+1)
kazu = [0] * (n+1)

check[0] = True

q = queue.Queue()
q.put(1)

ans = k


while not q.empty():
    tmp = q.get()
    check[tmp] = True
    kake = 0
    for i in range(len(ab[tmp])):
        if check[ab[tmp][i]] == True:
            continue
        kazu[ab[tmp][i]] += 1
        q.put(ab[tmp][i])
        ans *= k - kake - kazu[tmp] - 1
        ans %= mod
        
        kake += 1
    
print(ans)

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

ab = [[] for j in range(n+1)]
mod = 10**9 + 7

for i in range(n-1):
    a,b = map(int,input().split())
    ab[a].append(b)
    ab[b].append(a)
    
check = [False] * (n+1)
kazu = [0] * (n+1)

check[0] = True

q = queue.Queue()
q.put(1)

ans = k


while not q.empty():
    tmp = q.get()
    check[tmp] = True
    kake = 0
    for i in range(len(ab[tmp])):
        if check[ab[tmp][i]] == True:
            continue
        kazu[ab[tmp][i]] += 1
        q.put(ab[tmp][i])
        ans *= k - kake - kazu[tmp] - 1
        ans %= mod
        
        kake += 1
    
print(ans)

Solution (Python):
from collections import deque
n,k=map(int,input().split())
if n==1 and k==1:
    print(1)
    exit()
if k==1:
    print(0)
    exit()
g=[[] for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)
mod=10**9+7
ans=k
q=deque([0])
v=[0]*n
v[0]=1
vc=1
while q and vc<n:
    s=q.popleft()
    c=0
    if s==0:
        kai=k-1
    else:
        kai=k-2
    for es in g[s]:
        if v[es]==0:
            v[es]=1
            vc+=1
            c+=1
            q.append(es)
            ans*=kai
            ans%=mod
            kai-=1
print(ans%mod)

Solution (Python):



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

tree = [[] for i in range(n)]

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

kouho = [0]
used_tree = [0 for i in range(n)]
used_tree[0] = 1
ans = k
while kouho:
    head = kouho.pop()
    if head == 0:
        start = k-1
    else:
        start = k-2
    for tail in tree[head]:
        if used_tree[tail] == 0:
            ans *= start
            ans %= 1000000007
            start -= 1
            used_tree[tail] = 1
            kouho.append(tail)
print(ans)

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

def bfs(v):
  child=[0]*n
  next=[v]
  next2=set()
  visited=[-1]*n
  visitct=0
  while len(next)!=0 and visitct!=n:
    for i in range(len(next)):
      if visited[next[i]]==-1:
        visited[next[i]]=1
        visitct+=1
        for j in range(len(connection[next[i]])):
          if visited[connection[next[i]][j]]==-1:
            child[next[i]]+=1
            next2.add(connection[next[i]][j])
    next=list(next2)
    next2=set()
  return child

child=bfs(0)
ans=k
for i in range(n):
  if i==0:
    for j in range(k-1,k-1-child[i],-1):
      ans*=j
      ans%=mod
  else:
    for j in range(k-2,k-2-child[i],-1): 
      ans*=j
      ans%=mod
print(ans%mod)

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

def bfs(v):
  child=[0]*n
  next=[v]
  next2=set()
  visited=[-1]*n
  visitct=0
  while len(next)!=0 and visitct!=n:
    for i in range(len(next)):
      if visited[next[i]]==-1:
        visited[next[i]]=1
        visitct+=1
        for j in range(len(connection[next[i]])):
          if visited[connection[next[i]][j]]==-1:
            child[next[i]]+=1
            next2.add(connection[next[i]][j])
    next=list(next2)
    next2=set()
  return child

child=bfs(0)
ans=k
for i in range(n):
  if i==0:
    for j in range(k-1,k-1-child[i],-1):
      ans*=j
      ans%=mod
  else:
    for j in range(k-2,k-2-child[i],-1): 
      ans*=j
      ans%=mod
print(ans%mod)

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,k=map(int,input().split())
    E=[[] for _ in range(n)]
    for _ in range(n-1):
        a,b=map(int,input().split())
        a-=1; b-=1;
        E[a].append(b)
        E[b].append(a)

    dp=[1]*n
    dp[0]=k
    def dfs(v,p)->None:
        if(p!=-1):
            count=0
            for nv in E[v]:
                if(nv==p): continue
                dp[nv]=k-2-count
                count+=1
                dfs(nv,v)
        else:
            count=0
            for nv in E[v]:
                dp[nv]=k-1-count
                count+=1
                dfs(nv,v)

    dfs(0,-1)
    ans=1
    for i in range(n):
        ans*=dp[i]
        ans%=MOD
    print(ans)
resolve()

Solution (Python):
from collections import deque

mod = 10 ** 9 + 7

N, K, *AB = map(int, open(0).read().split())

E = [[] for _ in range(N + 1)]
for a, b in zip(*[iter(AB)] * 2):
    E[a].append(b)
    E[b].append(a)

ans = K
visited = [False] * (N + 1)
Q = deque([1])
while Q:
    v = Q.popleft()
    visited[v] = True

    k = K - 2 if v != 1 else K - 1
    for u in E[v]:
        if visited[u]:
            continue
        Q.append(u)
        ans = (ans * k) % mod
        k -= 1

print(ans)

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

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

graph = [[] for _ in range(N + 1)]
for a, b in zip(*[iter(ab)] * 2):
    graph[a].append(b)
    graph[b].append(a)

queue = deque([1])
checked = [False] * (N + 1)
checked[1] = True
answer = K
colors = K - 1

while queue:
    v = queue.popleft()
    for go in graph[v]:
        if not checked[go]:
            checked[go] = True
            answer *= colors
            answer %= mod
            queue.append(go)
            colors -= 1
    colors = K - 2

print(answer)

Solution (Python):
import sys
input=sys.stdin.readline
N,K=map(int,input().split())
P=[0 for i in range(N+1)]
C=[0 for i in range(N+1)]

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


for i in range(N-1):
    
    if P[Q[i][1]]==0:
        P[Q[i][1]]=Q[i][0]
        C[Q[i][0]]+=1
        for j in L[Q[i][1]]:
            if P[j[1]]==0:
                Q.append(j)
    

mod=10**9+7
ans=K
for i in range(C[1]):
    ans*=(K-i-1)
    ans%=mod
    

ANS=[0 for i in range(N+1)]
ANS[1]=ans
for i in range(2,N+1):
    if C[i]!=0:
        for j in range(C[i]):
            ans*=(K-j-2)
            
            ans%=mod
            ANS[i]=ans

print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
n,k = map(int,input().split())
t = [[] for _ in range(n)]
flag = [False for _ in range(n)]
for i in range(n-1):
    a,b = map(int,input().split())
    t[a-1].append(b-1)
    t[b-1].append(a-1)
res = 1
mod = 10**9+7

def dfs(s):
    global t
    global k
    global res
    global mod
    global flag
    if s == 0:
        res *= k
        tk = k-1
        for _ in range(len(t[s])):
            res *= tk
            res %= mod
            tk -= 1
    else:
        tk = k-2
        for _ in range(len(t[s])-1):
            res *= tk
            res %= mod
            tk -= 1
    flag[s] = True
    for g in t[s]:
        if not flag[g]:
            dfs(g)

if k ==1:
    if n>1:
        print(0)
    else:
        print(1)
elif k ==2:
    if n>2:
        print(0)
    else:
        print(2)
else:
    dfs(0)
    print(res % mod)

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

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

ans = 1
que = deque( [(1, 0, K)] )

while que:
    u, p, k = que.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
        que.append( (v, u, k_next) )
        k_next -= 1

print(ans)

Solution (Python):

from collections import deque


def dfs() -> int:
    cand, ret, MOD = K - 1, K, 10 ** 9 + 7
    queue, seen = deque([1]), [0] * (N + 1)
    seen[1] = 1
    while queue:
        v = queue.popleft()
        for u in G[v]:
            if not seen[u]:
                seen[u] = 1
                ret = (ret * cand) % MOD
                cand -= 1
                queue.append(u)
        cand = K - 2
    return ret


def main():
    global N, K, G
    N, K, *AB = map(int, open(0).read().split())
    G = [[] for _ in range(N + 1)]
    for v, u in zip(*[iter(AB)] * 2):
        G[v].append(u), G[u].append(v)
    ans = dfs()
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):

from collections import deque


def main():
    N, K, *AB = map(int, open(0).read().split())
    MOD = 10 ** 9 + 7
    G = [[] for _ in range(N + 1)]
    for v, u in zip(*[iter(AB)] * 2):
        G[v].append(u), G[u].append(v)
    queue = deque([1])
    seen = [0] * (N + 1)
    seen[1] = 1
    ans, cand = K, K - 1
    while queue:
        v = queue.popleft()
        for u in G[v]:
            if not seen[u]:
                seen[u] = 1
                ans = (ans * cand) % MOD
                cand -= 1
                queue.append(u)
        cand = K - 2
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque

mod = 10 ** 9 + 7

N, K, *AB = map(int, open(0).read().split())

E = [set() for _ in range(N + 1)]
for a, b in zip(*[iter(AB)] * 2):
    E[a].add(b)
    E[b].add(a)

ans = K

Q = deque([1])
while Q:
    v = Q.popleft()
    for i, u in enumerate(E[v], 1):
        ans *= (K - i - (v > 1))
        ans %= mod
        E[u].remove(v)
        Q.append(u)

print(ans)

Solution (Python):
import collections
N,K = map(int,input().split())
edge = collections.defaultdict(list)
for _ in range(N-1):
    a,b = map(int,input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
q = collections.deque()
q.append((0,-1))
M = K
while q:
    p,root = q.pop()
    if root == -1:
        for k in range(K-1,K-1-len(edge[p]),-1):
            M *= k
            M %= 10 ** 9 + 7
    else:
        for k in range(K-2,K-1-len(edge[p]),-1):
            M *= k
            M %= 10 ** 9 + 7
    for e in edge[p]:
        if e != root:
            q.append((e,p))
print(M)

Solution (Python):
import sys
from collections import deque
def chs(s,t,md):
    res = 1
    for i in range(s-t+1,s+1):
        res *= i
        res%=md
    """
    for i in range(1,t+1):
        i2 = pow(i,md-2,md)
        res*=i2
        res%=md
    """
    return(res)

mod = 10**9+7
n, k = map(int, input().split( ))
E = [[] for _ in range(n)]
Deg = [0]*n
for _ in range(n-1):
    a,b = map(int, input().split( ))
    a-=1
    b-=1
    E[a].append(b)
    E[b].append(a)

Done = [False]*n
dp = [1]*n

Q = deque()

Q.append(0)

Deg=[0]*n
P = [-1]*n
Done[0] = True

while Q:
    u = Q.popleft()
    for v in E[u]:
        if not Done[v]:
            Done[v] = True
            Deg[u] +=1
            if Deg[u]>k:
                print(0)
                sys.exit()
            P[v] = u
            Q.append(v)
ans = chs(k,Deg[0]+1,mod)
e0 = set(E[0])

for i in range(1,n):
    ans*=chs(k-2,Deg[i],mod)
    ans %=mod
    
print(ans)

Solution (Python):
def bfs(k):
    p=k
    frontier=[1]
    visited={1:1}
    while frontier:
        next=[]
        for u in frontier:
            if u==1:
                l=k-1
            else:
                l=k-2
            i=0
            if u in adj:
                for v in adj[u]:
                    if v not in visited:
                        visited[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 w 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)
print(bfs(k))

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

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

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

ans = 1
went = [0] * (N+1)
go = deque()
go.append([1, -2])

while len(go) > 0:
    now, brother = go.popleft()
    went[now] = 1
    ans *= (K-2-brother)
    ans %= MOD

    c = 0 if now != 1 else -1
    for b in tree[now]:
        if went[b] == 0:
            go.appendleft([b, c])
            c += 1

    if ans == 0:
        break

print(ans)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

MOD = 10**9 + 7

N,K = map(int,readline().split())
AB = map(int,read().split())

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

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

fact,fact_inv = make_fact(K+10,MOD)

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


deg = [len(x) for x in graph]
for i,x in enumerate(deg):
    if x == 1:
        break
root = i

parent = [0] * (N+1)
ts = [root]
stack = [root]
while stack:
    x = stack.pop()
    for y in graph[x]:
        if y == parent[x]:
            continue
        parent[y] = x
        stack.append(y)
        ts.append(y)

perm = np.zeros(N+K+10,np.int64)
perm[:K-1] = fact[K-2] * fact_inv[K-2::-1] % MOD
perm = perm.tolist()

dp = [1] * (N+1)
for v in ts[::-1]:
    if v == root:
        break
    d = deg[v]
    dp[v] *= perm[d-1]; dp[v] %= MOD
    p = parent[v]
    dp[p] *= dp[v]; dp[p] %= MOD

x = dp[root]
x *= K*(K-1)%MOD
x %= MOD
print(x)

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

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

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

def dfs(p, c1, c2, depth):
    C[p] = c1 + c2
    d = 0
    for np in graph[p]:
        if not checked[np]:
            checked[np] = True
            d += 1
            g = 1 if depth > 0 else 0
            dfs(np, d, g, depth+1)
        

dfs(0, 0, 0, 0)


mod = 10**9+7
ans = 1
for n in range(N):
    ans = ans * (K-C[n]) % mod

print(ans)

Solution (Python):



import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

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

lst = [-1]*n
lst[0] = k
que = deque()
que.append(0)
while que:
    v = que.popleft()
    if v == 0:
        cnt = 1
    else:
        cnt = 2
    for u in graph[v]:
        if lst[u] < 0:
            que.append(u)
            lst[u] = k - cnt
            cnt += 1
ans = 1
for i in lst:
    ans *= i
    ans %= mod
print(ans)

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

def main():
    n,k = map(int,input().split())
    mod = 10**9+7
    edge = [[] for _ in [None]*n]

    for _ in [None]*(n-1):
        a,b = map(int,input().split())
        edge[a-1].append(b-1)
        edge[b-1].append(a-1)
    
    p = -1
    pl = -1
    for i in range(n-1):
        if len(edge[i]) > pl:
            p = i
            pl = len(edge[i])
    
    par = [-2]*n
    par[p] = -1
    tank = []
    new = [p]
    while len(new) > 0:
        tank = []
        for e in new:
            for ko in edge[e]:
                if par[ko] == -2:
                    par[ko] = e
                    tank.append(ko)
        new = tank
    
    d = [-1]*n
    d[p] = k
    tank = []
    new = [p]
    while len(new) > 0:
        tank = []
        for e in new:
            if e == p:
                cnt = 1
            else:
                cnt = 2
            for go in edge[e]:
                if go != par[e]:
                    d[go] = k-cnt
                    cnt += 1
                    tank.append(go)
        new = tank
    
    res = 1
    for e in d:
        res = res*e%mod
    print(res)

if __name__ == '__main__':
    main()

Solution (Python):
def getlist():
	return list(map(int, input().split()))

from collections import defaultdict
import queue

const = 10 ** 9 + 7
INF = float("inf")

class Graph(object):
    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, a, b):
        self.graph[a].append(b)

    def get_nodes(self):
        return self.graph.keys()

class BFS(object):
	def __init__(self, graph, s, N, K):
		self.ans = 1
		self.g = graph.graph
		self.Q = queue.Queue()
		self.W = [len(self.g[i]) for i in range(N)]
		self.visit = ["No"] * (N + 1) 
		self.visit[s] = "Yes"
		
		for i in self.g[s]:
			self.Q.put(i)
		if self.W[0] + 1 > K:
			self.ans = 0
		else:
			for i in range(self.W[0] + 1):
				self.ans = (self.ans * (K - i)) % const

		
		while not self.Q.empty():
			v = self.Q.get()
			for i in self.g[v]:
				if self.visit[i] == "No":
					if self.W[i] + 1 > K:
						self.ans = 0
					else:
						for j in range(self.W[i] - 1):
							self.ans = (self.ans * (K - 2 - j)) % const
					self.Q.put(i)
					self.visit[i] = "Yes"

	def answer(self):
		return self.ans


N, K = getlist()
G = Graph()
for i in range(N - 1):
	a, b = getlist()
	G.add_edge(a - 1, b - 1)
	G.add_edge(b - 1, a - 1)
s = 0


W = BFS(G, 0, N, K)
print(W.answer())

Solution (Python):
from collections import deque

mod = 10 ** 9 + 7

n, k = map(int, input().split())
es = tuple(set() for _ in range(n))
for _ in range(n - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    es[a].add(b)
    es[b].add(a)

ans = k

q = deque()

can_use = k - 1


for u in es[0]:
    ans = (ans * can_use) % mod
    can_use -= 1
    q.append((u, 0))

while q:
    v, pr = q.popleft()
    can_use = k - 2
    
    
    for u in es[v]:
        if u == pr:
            continue
        ans = (ans * can_use) % mod
        can_use -= 1
        q.append((u, v))

print(ans)

Solution (Python):
from collections import deque

mod = 10 ** 9 + 7

n, k = map(int, input().split())
es = tuple(set() for _ in range(n))
for _ in range(n - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    es[a].add(b)
    es[b].add(a)

ans = k

q = deque()

can_use = k - 1


for u in es[0]:
    ans = (ans * can_use) % mod
    can_use -= 1
    q.append((u, 0))

while q:
    v, pr = q.popleft()
    can_use = k - 2
    
    
    for u in es[v]:
        if u == pr:
            continue
        ans = (ans * can_use) % mod
        can_use -= 1
        q.append((u, v))

print(ans)