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 bisect
import collections
import copy
import functools
import heapq
import math
import sys
from collections import deque
from collections import defaultdict
input = sys.stdin.readline
sys.setrecursionlimit(10**9)
INF = float("inf")
MOD = 10**9+7

kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]
 
gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]
 
def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

def nPr(n,r):
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

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

not_visited = [-1]*N
not_visited[0] = 0
stack = deque()
stack.append(0)

ans = K
loop = 1
while stack:
    now = stack.popleft()
    c = len(lines[now])
    if loop == 1:
        ans *= nPr(K-1,c)
    else:
        ans *= nPr(K-2,c-1)
    for nex in lines[now]:
        if not_visited[nex] == -1:
            not_visited[nex] =  not_visited[now] + 1
            stack.append(nex)
    loop += 1
    ans %= MOD

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
N,K = map(int,input().split())
AB = [tuple(map(int,input().split())) for i in range(N-1)]

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

MOD = 10**9+7
ans = K
def rec(v,p=-1,d=0):
    global ans
    k = K-2 if d else K-1
    for to in es[v]:
        if to==p: continue
        ans *= k
        ans %= MOD
        k -= 1
        rec(to,v,d+1)
rec(0)
print(ans)

Solution (Python):





from collections import deque

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, b = a-1, b-1
    graph[a].append(b)
    graph[b].append(a)


q = deque()
seen = [False]*n
parent = [-1]*n
q.append(0)
seen[0] = True
parent[0] = 0
ret = k
while len(q)>0:
    cur = q.popleft()
    if cur == 0:
        cnt = k-1
    else:
        cnt = k-2
    for i in graph[cur]:
        if seen[i]==False:
            seen[i] = True
            
            parent[i] = cur
            q.append(i)
            ret *= cnt
            ret %= mod
            cnt -= 1
print(ret)

Solution (Python):




from collections import deque
mod = 10**9+7
N = 10**6                   
g1 = [1]*(N+1)              
g2 = [1]*(N+1)              
for i in range(2, N + 1 ): 
    g1[i] = ( g1[i-1] * i ) % mod
g2[N] = pow(g1[-1], mod-2, mod)
for i in range(N, 0, -1):
    g2[i-1] = ( g2[i] * i ) % mod

def nCr(n, r):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

def nPr(n, r):
    if ( r<0 or r>n ):
        return 0
    return g1[n] * g2[n-r] % mod

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

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


q = deque()
seen = [False]*n
parent = [-1]*n
q.append(0)
seen[0] = True
parent[0] = 0
ret = k
while len(q)>0:
    cur = q.popleft()
    if cur == 0:
        cnt = k-1
    else:
        cnt = k-2
    for i in graph[cur]:
        if seen[i]==False:
            seen[i] = True
            
            parent[i] = cur
            q.append(i)
            ret *= cnt
            ret %= mod
            cnt -= 1
print(ret)

Solution (Python):
from collections import deque

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

stack=deque([[0,K]])
check = [True]*N
check[0] = False
ans = 1
while len(stack):
    u,k = stack.popleft()
    ans = (ans*k)%mod
    if u == 0:
        k_next = K-1
    else:
        k_next = K-2
    for v in root[u]:
        if check[v]:
            check[v] = False
            stack.append([v,k_next])
            k_next -= 1
    
print(ans)

Solution (Python):

"""
Created on Tue Aug 25 08:44:21 2020

@author: teppe
"""

from collections import deque

def prepare(n, MOD):
 
    
    f = 1
    factorials = [1]  
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    
    inv = pow(f, MOD - 2, MOD)
    
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
     
    return factorials, invs

MOD = 10**9+7
fact, fact_inv = prepare(10+10**5, MOD)

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


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)
 
colored = [False]*n
colored[0] = True
num = len(e[0])
ans = perm(k, 1+num)
d = deque()
for i in e[0]:
    colored[i] = True
    d.append(i)
while d:
    f = d.pop()
    num = len(e[f]) - 1
    if num == 0:
        continue
    ans *= perm(k-2, num)
    ans %= MOD
    for i in e[f]:
        if not colored[i]:
            colored[i] = True
            d.appendleft(i)
print(ans % MOD)

Solution (Python):
n,k=map(int,input().split())
e=[[]for _ in range(n+1)]
for _ in range(n-1):
  a,b=map(int,input().split())
  e[a]+=[b]
  e[b]+=[a]
mod=10**9+7
vis=[1]*(n+1)
vis[1]=0
q=[1]
ans=k
while q:
  now=q.pop()
  i=0
  for to in e[now]:
    if vis[to]:
      vis[to]=0
      ans*=max(k-i-1-(now!=1),0)
      ans%=mod
      q+=[to]
      i+=1
print(ans)

Solution (Python):
import sys
import itertools

import time
import math
import heapq
from collections import defaultdict
from collections import Counter
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines



import sys
import itertools

import time
import math
import heapq
from collections import defaultdict
from collections import Counter
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


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

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

from collections import deque
q = deque([])
q.append(0)
ps = [0] * N
ps[0] = K
visited = [False] * N
visited[0] = True
while len(q) > 0:
    v = q.popleft()
    now = K - 2
    if v == 0:
        now = K - 1
    for u in adj[v]:
        if visited[u]:
            continue
        visited[u] = True
        ps[u] = now
        now -= 1
        q.append(u)
ans = 1
for p in ps:
    ans *= p
    ans %= MOD
print(ans % MOD)

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    import queue
    mod=10**9+7
    N,K=MI()

    

    def calc(n, r, mod):
        if (r < 0) or (n < r):
            return 0
        return (fact[n] * factinv[n-r])%mod

    fact=[1,1]
    factinv=[1,1]
    inv=[0,1]

    for i in range(2, 10**5+5 + 1):
        fact.append((fact[-1] * i) % mod)
        inv.append((-inv[mod % i] * (mod // i)) % mod)
        factinv.append((factinv[-1] * inv[-1]) % mod)
    
    adj=[[]for _ in range(N)]
    for i in range(N-1):
        a,b=MI()
        a-=1
        b-=1
        adj[a].append(b)
        adj[b].append(a)
    
    
    ans=K
    
    q=queue.Queue()
    q.put((0,0,-1))
    
    while not q.empty():
        v,d,p=q.get()
        cnt=0
        for nv in adj[v]:
            if nv!=p:
                cnt+=1
                q.put((nv,d+1,v))
            
        if cnt!=0:
            np=2
            if d==0:
                np=1
                
            ans=(ans*calc(K-np,cnt,mod))%mod
        
    print(ans)

        
    

main()

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
mod = 10**9+7
N,K = map(int,input().split())
g = [[] for _ in range(N)]
for i in range(N-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)


ans = K
def rec(c,p):
    global ans
    if c == 0:
        for i in range(len(g[0])):
            ans *= K-i-1
            ans %= mod
        for v in g[c]:
            if v != p:
                rec(v,c)
    else:
        for i in range(len(g[c])-1):
            ans *= K-i-2
            ans %= mod
        for v in g[c]:
            if v != p:
                rec(v,c)


rec(0,0)
print(ans)

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

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

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

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

ans = []
def wfs(now,back):
    if now != 0:
        cnt = K - 2 
    else:
        cnt = K - 1
    for nxt in tree[now]:
        if nxt != back:
            ans.append(cnt)
            cnt = cnt - 1
            wfs(nxt,now)

ans.append(K)
wfs(0,-1)

ans2 = 1
for j in range(len(ans)):
    ans2 = (ans2 * ans[j]) % (10**9+7)
print(ans2)

Solution (Python):
from collections import deque
mod = 10**9+7
N,K = map(int,input().split())
Tree = [[] for _ in range(N+1)]
for i in range(N-1):
    ai,bi = map(int,input().split())
    Tree[ai].append(bi)
    Tree[bi].append(ai)
d = deque([1])
parent = [-1]*(N+1)
permutation = [1,K-2]
for i in range(K-3):
    permutation.append(permutation[-1]*(K-3-i)%mod)
while d:
    x = d.popleft()
    for y in Tree[x]:
        if parent[x] != y:
            parent[y] = x
            d.append(y)
    if x == 1:
        if len(Tree[x]) > K-1:
            ans = 0
        else:
            ans = 1
            for i in range(len(Tree[x])+1):
                ans *= K-i
                ans %= mod
    else:
        if len(Tree[x]) > K-1:
            ans = 0
        else:
            ans *= permutation[len(Tree[x])-1]
            ans %= mod
print(ans)

Solution (Python):
def main():
    from collections import defaultdict, deque
    import sys
    mod = 10**9+7
    N, K = map(int, input().split())
    dic= defaultdict(list)

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

    seen = [-1]*N
    seen[0]=0
    ans = K
    
    for i in range(len(dic[1])):
        if K-i-1<=0:
            print(0)
            sys.exit()
        ans *= K-i-1
        ans %= mod

    queue = deque(dic[1])
    for  p in dic[1]:
        seen[p-1]=0

    while queue:
        bla= queue.popleft()
        for j in range(len(dic[bla])-1):
            if K-j-2<=0:
                print(0)
                sys.exit()
            ans *= K-j-2
            ans %= mod

        for i in dic[bla]:
            if len(dic[i])==1:
                continue
            if seen[i-1]==-1:
                queue.append(i)
                seen[i-1]=0
    print(ans)
main()

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

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

if K==1:
  if N==1:
    print(1)
  else:
    print(0)
  exit()
  
P=[0]*(K-1)
P[K-2]=K-2
for i in range(K-3,0,-1):
  P[i]=P[i+1]*i%MOD
  
def PPP(start,num):
  if start<num:
    return 0
  if start==K-2:
    return P[start-num+1]
  if start==K-1:
    return P[start-num+2]*(K-1)%MOD
  
ans=1

def draw(parent,nord):
  global ans
  children=len(branch[nord])-(parent !=-1)
  if children==0:
    return
  
  ans=ans*PPP(K-1-(parent !=-1),children)%MOD
  for b in branch[nord]:
    if b != parent:
      draw(nord,b)

for i in range(len(branch[0])+1):
  ans=ans*(K-i)%MOD
for bra in branch[0]:
  draw(0,bra)
print(ans)

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

N,K=map(int,input().split())
SIZE=10**5+1; MOD=10**9+7 
 
SIZE += 1
inv = [0]*SIZE  
fac = [0]*SIZE  
finv = [0]*SIZE 
inv[1] = 1
fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
for i in range(2,SIZE):
  inv[i] = MOD - (MOD//i)*inv[MOD%i]%MOD
  fac[i] = fac[i-1]*i%MOD
  finv[i]= finv[i-1]*inv[i]%MOD

def narabekae(n,r): 
  if n-r<0:
    return 0
  return fac[n]*finv[n-r]%MOD

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

ans=1

def draw(parent,nord):
  global ans
  children=len(branch[nord])-(parent !=-1)
  if children==0:
    return
  
  ans=ans*narabekae(K-1-(parent !=-1),children)%MOD
  for b in branch[nord]:
    if b != parent:
      draw(nord,b)

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

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

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

if K==1:
  if N==1:
    print(1)
  else:
    print(0)
  exit()
  
P=[0]*(K-1)
P[K-2]=K-2
for i in range(K-3,0,-1):
  P[i]=P[i+1]*i%MOD
  
def PPP(start,num):
  if start<num:
    return 0
  if start==K-2:
    return P[start-num+1]
  if start==K-1:
    return P[start-num+2]*(K-1)%MOD
  
ans=1

def draw(parent,nord):
  global ans
  children=len(branch[nord])-(parent !=-1)
  if children==0:
    return
  
  ans=ans*PPP(K-1-(parent !=-1),children)%MOD
  for b in branch[nord]:
    if b != parent:
      draw(nord,b)

for i in range(len(branch[0])+1):
  ans=ans*(K-i)%MOD
for bra in branch[0]:
  draw(0,bra)
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
class Combination:
  def __init__(self, n_max, mod=10**9+7):
    self.mod = mod
    self.modinv = self.make_modinv_list(n_max)
    self.fac, self.facinv = self.make_factorial_list(n_max)

  def __call__(self, n, r):
    return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

  def make_factorial_list(self, n):
    
    
    fac = [1]
    facinv = [1]
    for i in range(1, n+1):
      fac.append(fac[i-1] * i % self.mod)
      facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
    return fac, facinv

  def make_modinv_list(self, n):
    
    modinv = [0] * (n+1)
    modinv[1] = 1
    for i in range(2, n+1):
        modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
    return modinv

N,K = map(int,input().split())
adj = [ [ ]for _ in range(N) ]
comb = Combination(10**5)

def nPr(n,r):
  if n < r: return 0
  return comb(n, r) * comb.fac[r]

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

def dfs(v, p=-1):
  global ans
  c = 0
  for nei in adj[v]:
    if nei == p: continue
    c += 1
    dfs(nei, v)

  nk = K-1 if p==-1 else K-2
  ans *= nPr(nk, c)
  ans %= 10**9+7

ans = K
dfs(0)
print(ans)

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

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

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

    G[a].append(b)
    G[b].append(a)



def dfs(now, par):
    if K < len(G[now]): return 0

    res = 1

    if par == -1:
        colors = K-1
        for i in range(len(G[now])):
            res *= colors-i
            res %= MOD
    else:
        colors = K-2
        for i in range(len(G[now])-1):
            res *= colors-i
            res %= MOD

    for c in G[now]:
        if c == par: continue
        
        res *= dfs(c, now)
        res %= MOD
    
    return res

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

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

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

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

    G[a].append(b)
    G[b].append(a)



def dfs(now, par):
    if K < len(G[now]): return 0

    res = 1

    if par == -1:
        colors = K-1
        for i in range(len(G[now])):
            res *= colors-i
            res %= MOD
    else:
        colors = K-2
        for i in range(len(G[now])-1):
            res *= colors-i
            res %= MOD

    for c in G[now]:
        if c == par: continue
        
        res *= dfs(c, now)
        res %= MOD
    
    return res

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

Solution (Python):
import sys
from collections import deque
def input(): return sys.stdin.readline().rstrip()

def per(n, r, mod=10**9+7):  
    per = 1
    for i in range(r):
        per = per*(n-i) % mod
    return per
 
n, k = map(int, input().split())
mod=10**9+7
graph = [[] for _ in range(n+1)]

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

dist = [-1] * (n+1)
dist[0] = 0
dist[1] = 0

d = deque()
d.append(1)
ans=k
while d:
    v = d.popleft()
    cnt=0
    for i in graph[v]:
        if dist[i] != -1:
            continue
        dist[i] = dist[v] + 1
        d.append(i)
        cnt+=1
    if cnt>0:
        if v==1:
            ans=ans*per(k-1,cnt)%mod
        else:
            ans=ans*per(k-2,cnt)%mod
    


print(ans)

Solution (Python):
class Combination:                                      
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        f = 1
        self.fac = fac = [f]
        for i in range(1, n_max+1):                     
            f = f * i % mod                             
            fac.append(f)                               
        f = pow(f, mod-2, mod)                          
                                                        
        self.facinv = facinv = [f]
        for i in range(n_max, 0, -1):                   
            f = f * i % mod
            facinv.append(f)
        facinv.reverse()


    def __call__(self, n, r):  
        if not 0 <= r <= n: return 0
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def P(self, n, r):
        if not 0 <= r <= n: return 0
        return self.fac[n] * self.facinv[n-r] % self.mod


import sys
input = sys.stdin.readline

mod=10**9+7
N, K = map(int, input().split())
comb = Combination(K)
edges = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    edges[a].append(b)
    edges[b].append(a)

res = K
res *= comb.P(K-1,len(edges[0]))
res %= mod
next_set = edges[0]
visited = set([0]+edges[0])
while next_set:
    p = next_set.pop()
    cnt = 0
    for q in edges[p]:
        if q in visited:
            continue
        cnt += 1
        visited.add(q)
        next_set.append(q)
    res *= comb.P(K-2,cnt)
    res %= mod
print(res%mod)

Solution (Python):
import sys
import re
import math
import collections
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal
import statistics
import queue



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


ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))
nb = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))





def main():
    n, k = ns()
    e = [[] for _ in range(n)]
    for _ in range(n - 1):
        a, b = ns()
        a, b = a - 1, b - 1
        e[a].append(b)
        e[b].append(a)

    table = [True for _ in range(n)]
    perm = [1]
    for i in range(k - 2, -1, -1):
        perm.append(perm[-1] * i % MOD)

    table[0] = False
    que = collections.deque(e[0])
    ans = k
    for i in range(len(e[0])):
        table[e[0][i]] = False
        ans *= k - i - 1
        ans %= MOD

    while len(que) > 0:
        for _ in range(len(que)):
            q = que.popleft()
            cnt = 0
            for i in range(len(e[q])):
                tmp = e[q][i]
                if table[tmp]:
                    table[tmp] = False
                    cnt += 1
                    que.appendleft(tmp)
            ans *= perm[min(len(perm) - 1, cnt)]
            ans %= MOD

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
import re
import math
import collections
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal
import statistics
import queue



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


ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))
nb = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))





def main():
    n, k = ns()
    e = [[] for _ in range(n)]
    for _ in range(n - 1):
        a, b = ns()
        a, b = a - 1, b - 1
        e[a].append(b)
        e[b].append(a)

    table = [True for _ in range(n)]
    perm = [1]
    for i in range(k - 2, -1, -1):
        perm.append(perm[-1] * i % MOD)

    table[0] = False
    que = collections.deque(e[0])
    ans = k
    for i in range(len(e[0])):
        table[e[0][i]] = False
        ans *= k - i - 1
        ans %= MOD

    while len(que) > 0:
        for _ in range(len(que)):
            q = que.popleft()
            cnt = 0
            for i in range(len(e[q])):
                tmp = e[q][i]
                if table[tmp]:
                    table[tmp] = False
                    cnt += 1
                    que.appendleft(tmp)
            ans *= perm[min(len(perm) - 1, cnt)]
            ans %= MOD

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
mod = 10 ** 9 + 7
n, k = map(int, input().split())
if n == 1:
    print(k)
    quit()

ans = k * (k - 1)
branch_n = [0] * n
for _ in range(n-1):
     nodes = map(lambda x : int(x) - 1, input().split())
     for i in nodes:
        branch_n[i] += 1
        if branch_n[i] > 1:
            ans = ans * (k - branch_n[i]) % mod
print(ans)

Solution (Python):
import networkx as nx

def factorial(n, mod):
    fac = [0] * (n + 1)
    inv = [0] * (n + 1)
    fac[0], inv[0] = 1, 1
    for i in range(1, n + 1):
        fac[i] = fac[i-1] * i % mod
        inv[i] = inverse(fac[i], mod)
    return fac, inv

def inverse(a, mod):
    a %= mod 
    p = mod
    x, y = 0, 1
    while a > 0:
        n = p // a
        p, a = a, p % a, 
        x, y = y, x - n * y
    return x % mod 

mod = 1000000007

n, k = map(int, input().split())
graph = nx.Graph()
graph.add_nodes_from(range(n))

graph.add_edges_from([tuple(map(lambda x : int(x) - 1, input().split())) for _ in range(n-1)])
if nx.degree(graph)[0] + 1 > k:
    print(0)
    quit()

fac, inv = factorial(k, mod)
ans = fac[k] * inv[k - nx.degree(graph)[0] - 1] % mod 
for parent, child in nx.dfs_edges(graph, 0): 
    m = nx.degree(graph)[child]
    if m + 1 > k:
        print(0)
        quit()
    ans = ans * fac[k-2] % mod * inv[k-1-m] % mod
print(ans)

Solution (Python):
import networkx as nx

def factorial(n, mod):
    fac = [0] * (n + 1)
    inv = [0] * (n + 1)
    fac[0], inv[0] = 1, 1
    for i in range(1, n + 1):
        fac[i] = fac[i-1] * i % mod
        inv[i] = inverse(fac[i], mod)
    return fac, inv

def inverse(a, mod):
    a %= mod 
    p = mod
    x, y = 0, 1
    while a > 0:
        n = p // a
        p, a = a, p % a, 
        x, y = y, x - n * y
    return x % mod 

mod = 1000000007

n, k = map(int, input().split())
graph = nx.Graph()
graph.add_nodes_from(range(n))
for _ in range(n-1):
    a, b = map(lambda x : int(x) - 1, input().split())
    graph.add_edge(a, b)
if nx.degree(graph)[0] + 1 > k:
    print(0)
    quit()

fac, inv = factorial(k, mod)
ans = fac[k] * inv[k - nx.degree(graph)[0] - 1] % mod 
for parent, child in nx.dfs_edges(graph, 0): 
    m = nx.degree(graph)[child]
    if m + 1 > k:
        print(0)
        quit()
    ans = ans * fac[k-2] % mod * inv[k-1-m] % mod
print(ans)

Solution (Python):
def factorial(n, mod):
    fac = [0] * (n + 1)
    inv = [0] * (n + 1)
    fac[0], inv[0] = 1, 1
    for i in range(1, n + 1):
        fac[i] = fac[i-1] * i % mod
        inv[i] = inverse(fac[i], mod)
    return fac, inv

def inverse(a, mod):
    a %= mod 
    p = mod
    x, y = 0, 1
    while a > 0:
        n = p // a
        p, a = a, p % a, 
        x, y = y, x - n * y
    return x % mod 

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

branch_n = [0] * n
for i in range(n-1):
    a, b = map(lambda x : int(x) - 1, input().split())
    nodes[a].append(b)
    nodes[b].append(a)

if len(nodes[0]) >= k:
    print(0)
    quit()
stack = nodes[0][:]
visited = {0}
fac, inv = factorial(k, mod)
ans = fac[k] * inv[k-len(nodes[0])-1] % mod
while stack:
    i = stack.pop()
    visited.add(i)
    m = len(nodes[i])
    if m >= k:
        print(0)
        quit()
    ans = ans * fac[k-2] % mod * inv[k-1-m] % mod
    for j in nodes[i]:
        if not j in visited:
            stack.append(j)
print(ans)

Solution (Python):

from collections import deque

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

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

MAX = 10 ** 5 + 1
MOD = 10 ** 9 + 7


fac = [0] * (MAX + 1)
fac[0] = 1
fac[1] = 1


inv = [0] * (MAX + 1)
inv[1] = 1


finv = [0] * (MAX + 1)
finv[0] = 1
finv[1] = 1

for i in range(2, MAX + 1):
    fac[i] = fac[i - 1] * i % MOD
    inv[i] = MOD - inv[MOD % i] * (MOD // i) % MOD
    finv[i] = finv[i - 1] * inv[i] % MOD


def comb(n, k):
    if n < k or k < 0:
        return 0
    return (fac[n] * finv[k] * finv[n - k]) % MOD


visited = [False] * (N + 1)
visited[1] = True
ans = K * comb(K - 1, len(graph[1])) * fac[len(graph[1])] % MOD  
q = deque([1])
while q:
    u = q.popleft()
    for v in graph[u]:
        if visited[v]:
            continue

        ans *= comb(K - 2, len(graph[v]) - 1) * fac[len(graph[v]) - 1]
        ans %= MOD
        visited[v] = True
        q.append(v)

print(ans)

Solution (Python):
"""
あ
あ
あ
あ
あ
あ
あ
あ
あ
あ
あ
あ
あ
あ
あ
あ
あ
あ
あ
あ
あ
あ
あ
あ
あ
あ
あ
あ
あ
あ
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
みたな？































"""
import sys
input = sys.stdin.readline
N, K  = map(int, input().split())
e = [[] for _ in range(N + 1)]
mod = 10 ** 9 + 7
for _ in range(N - 1):
  u, v = map(int, input().split())
  e[u].append(v)
  e[v].append(u)

class Factorial:
  def __init__(self, n, mod):
    self.mod = mod
    self.f = [1]
    for i in range(1, n + 1):
      self.f.append(self.f[-1] * i % mod)
    self.i = [pow(self.f[-1], mod - 2, mod)]
    for i in range(1, n + 1)[: : -1]:
      self.i.append(self.i[-1] * i % mod)
    self.i.reverse()
  def factorial(self, i):
    return self.f[i]
  def ifactorial(self, i):
    return self.i[i]
  def combi(self, n, k):
    return self.f[n] * self.i[n - k] % self.mod * self.i[k] % self.mod
  def permi(self, n, k):
    return self.f[n] * self.i[n - k] % self.mod

f = Factorial(N + K, mod)
s = [1]
vis = [0] * (N + 1)
res = f.permi(K, len(e[1]) + 1)
if K < len(e[1]) + 1: res = 0
while len(s):
  x = s.pop()
  vis[x] = 1
  for y in e[x]:
    if vis[y]: continue
    s.append(y)
    if K - 2 < 0 or (K - 2 < len(e[y]) - 1): res = 0
    res *= f.permi(K - 2, len(e[y]) - 1)
    res %= mod
print(res)

Solution (Python):
import sys
N,K=map(int, input().split())
mod=10**9+7
G={}
for i in range(N):
  G[i+1]=[]
for i in range(N-1):
  a,b=map(int, input().split())
  G[a].append(b)
  G[b].append(a)

for i in range(N):
  if len(G[i+1])>=K:
    print(0)
    exit()

def nPr(n,r):
  res=1
  for i in range(r):
    res*=(n-i)
    res%=mod
  return res

from collections import deque
q=deque([(1,0)])
ans=K
while q:
  n,m=q.pop()
  if m==0:
    ans*=nPr(K-1,len(G[n]))
    ans%=mod
    for d in G[n]:
      q.appendleft((d,n))
  else:
    ans*=nPr(K-2,len(G[n])-1)
    ans%=mod
    for d in G[n]:
      if d!=m:
        q.appendleft((d,n))
print(ans)

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

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_adjlist_nond(n, edges):
    res = [[] for _ in range(n+1)]
    for edge in edges:
        res[edge[0]].append(edge[1])
        res[edge[1]].append(edge[0])
    return res


def main():
    N, K = NMI()
    edges = [NLI() for _ in range(N-1)]
    tree = make_adjlist_nond(N, edges)
    stack = deque()
    stack.append(1)
    ans = K
    seen = [False] * (N+1)
    while stack:
        now = stack.pop()
        seen[now] = True
        tmp = K - 2
        if now == 1:
            tmp += 1
        cnt = 0
        for i, goto in enumerate(tree[now]):
            if seen[goto]:
                cnt += 1
                continue
            ans = ans * (tmp - i + cnt) % MOD
            stack.append(goto)

    print(ans % MOD)


if __name__ == "__main__":
    main()