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):
n, k = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n - 1)]

mod = 10 ** 9 + 7

from collections import defaultdict
g = defaultdict(set)
for a, b in ab:
    g[a-1].add(b-1)
    g[b-1].add(a-1)

ans = k
q = [0]
visited = set([0])

while q:
    cur = q.pop()

    if cur == 0:
        tmp = k - 1
    else:
        tmp = k - 2
    for target in g[cur]:
        if target not in visited:
            ans = (ans * tmp) % mod
            tmp -= 1

            q.append(target)
            visited.add(target)

print(ans)

Solution (Python):
from collections import deque
import sys
input = sys.stdin.readline
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    return g1[n] * g2[n-r]  % mod

mod = 10**9+7 
N = 10**5
g1 = [1, 1] 
g2 = [1, 1] 
inverse = [0, 1] 

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

N,K=map(int,input().split())
ki=[[] for f in range(N)]
for i in range(N-1):
 a,b = map(int,input().split())
 ki[a-1].append(b-1)
 ki[b-1].append(a-1)
stack = deque([0])
check = [0]*N 
c=0
t=0
ans=1
while stack != deque([]) :
 a=stack.popleft()
 check[a]=1
 if len(ki[a])+1>K:
  t=1
  break
 else:
  for i in ki[a]:
   if check[i]==0:
    stack.append(i)
  ans*=cmb(K-c,len(ki[a])+1-c,mod)
  ans%=(10**9+7)
  c=2
if t==1:
 print(0)
else:
 print(ans)

Solution (Python):








import sys
from collections import defaultdict

sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))



def read_a_int(): return int(read())


def read_ints(): return list(map(int, read().split()))


MOD = 10**9 + 7

N, K = read_ints()
tree = defaultdict(lambda: [])
for _ in range(N - 1):
    a, b = read_ints()
    a, b = mina(a, b)
    tree[a].append(b)
    tree[b].append(a)


def perm_mod(n, r, mod=MOD):
    if n < r:  
        return 0

    ret = 1
    for _ in range(r):
        ret *= n
        ret %= mod
        n -= 1
    return ret


def dfs(u, p):  
    if len(tree[u]) == 1 and tree[u][0] == p:
        
        return 1
    ret = 1  
    for to in tree[u]:
        if to == p:
            continue
        ret *= dfs(to, u)
        ret %= MOD
    if p == -1:
        ret *= perm_mod(K, len(tree[u]) + 1)
    else:
        ret *= perm_mod(K - 2, len(tree[u]) - 1)

    return ret % MOD


print(dfs(0, -1))

Solution (Python):








import sys
from collections import defaultdict

sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))



def read_a_int(): return int(read())


def read_ints(): return list(map(int, read().split()))


MOD = 10**9 + 7

N, K = read_ints()
tree = defaultdict(lambda: [])
for _ in range(N - 1):
    a, b = read_ints()
    a, b = mina(a, b)
    tree[a].append(b)
    tree[b].append(a)


def perm_mod(n, r, mod=MOD):
    
    ret = 1
    for _ in range(r):
        ret *= n
        ret %= mod
        n -= 1
    return ret


def dfs(u, p):  
    if len(tree[u]) == 1 and tree[u][0] == p:
        
        return 1
    ret = 1  
    for to in tree[u]:
        if to == p:
            continue
        ret *= dfs(to, u)
        ret %= MOD
    if p == -1:
        ret *= perm_mod(K, len(tree[u]) + 1)
    else:
        ret *= perm_mod(K - 2, len(tree[u]) - 1)

    return ret % MOD


print(dfs(0, -1))

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


MOD = 10**9+7
 
MAXN = N+5+K
fac = [1,1] + [0]*MAXN
finv = [1,1] + [0]*MAXN
inv = [0,1] + [0]*MAXN
for i in range(2,MAXN+2):
    fac[i] = fac[i-1] * i % MOD
    inv[i] = -inv[MOD%i] * (MOD // i) % MOD
    finv[i] = finv[i-1] * inv[i] % MOD
 

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





q  = []
used = [False] * N
used[0] = True
for nxt in es[0]:
    q.append(nxt)
    used[nxt] = True


ans = K * nPr(K-1, len(es[0]))
ans %= MOD
while q:
    curr = q.pop()
    ans *= nPr(K-2, len(es[curr]) - 1)
    ans %= MOD
    for nxt in es[curr]:
        if used[nxt]:
            continue

        used[nxt] = True
        q.append(nxt)


print(ans)

Solution (Python):
import sys 
sys.setrecursionlimit(10**6)
n, k = map(int, input().split())
edges = [[] for i in range(n)]
for i in range(n-1):
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    edges[a].append(b)
    edges[b].append(a)
    
mod = 10**9 + 7
def P(x,y):
    
    
    cnt = 0
    ans = 1
    waru = 1
    while cnt < y:
        ans *= (x-cnt)
        ans %= mod
        cnt += 1
    return ans%mod


ans = 1
def dfs(v,p):
    global ans
    us = edges[v]
    for u in us:
        if u == p: continue
        if len(edges[u]) == 1: ans *= 1
        ans *= P(k-2, len(edges[u])-1)   
        ans %= mod
        dfs(u,v)

dfs(0,-1)
n0 = len(edges[0])
a = P(k,n0+1)

ans *= a
ans %= mod
print(ans)

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

def iig(vn, en):
    res = [[] for _ in range(vn)]
    for _ in range(en):
        ai, bi = map(lambda x: int(x) - 1, input().split())
        res[ai].append(bi)
        res[bi].append(ai)
    return res

def sep_pc(graph, root=0):
    parent = [-1 for _ in range(n)]
    children = [None for _ in range(n)]
    def f(x, p):
        parent[x] = p
        children[x] = [y for y in graph[x] if y != p]
        for y in graph[x]:
            if y != p:
                f(y, x)
        return
    f(root, -1)
    return parent, children

def itree(n, root=0):
    return sep_pc(iig(n, n - 1), root)

mod = 10**9 + 7

fact_range = 10**5 + 3
facts = [1] * (fact_range + 1)
for i in range(0, fact_range):
    facts[i+1] = facts[i] * (i + 1) % mod

ifacts = [1] * (fact_range + 1)
ifacts[fact_range] = pow(facts[fact_range], mod - 2, mod)
for i in range(fact_range, 0, -1):
    ifacts[i-1] = ifacts[i] * i % mod

n, k = map(int, input().split())
p, c = itree(n)
def dfs(i=0, cur=k, avail=k-1):
    sz = len(c[i])
    if avail <= 0 and sz > 0 or sz > avail:
        return 0
    cur = cur * facts[avail] * ifacts[avail - sz] % mod
    for u in c[i]:
        cur = dfs(u, cur, k - 2)
    return cur
print(dfs())

Solution (Python):
from sys import stdin
from collections import deque
def main():
    
    readline=stdin.readline
    mod=10**9+7
    n,k=map(int,readline().split())
    G=[[] for _ in range(n)]
    for i in range(n-1):
        a,b=map(lambda x:int(x)-1,readline().split())
        G[a].append(b)
        G[b].append(a)

    ans=k
    stack=deque([0])
    flags=[False]*n
    flags[0]=True
    
    while len(stack)>0:
        now=stack.pop()
        if now==0:
            ans*=P(k-1,len(G[0]),mod)
            ans%=mod
        else:
            ans*=P(k-2,len(G[now])-1,mod)
            ans%=mod
        for nex in G[now]:
            if flags[nex]==False:
                flags[nex]=True
                stack.append(nex)

    print(ans)

def P(n,k,mod):
    res=1
    for m in range(n,n-k,-1):
        res*=m
        res%=mod
    return res

if __name__=="__main__":
    main()

Solution (Python):
from collections import deque

def main():
    N, K = map(int, input().split())
    edge = [[] for _ in range(N)]
    MOD = 10 ** 9 + 7
    for _ in range(N-1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        edge[a].append(b)
        edge[b].append(a)
    
    
    ans = K
    visited = [False] * N
    q = deque([[0,K]])
    while q:
        s, color = q.popleft()
        if visited[s]:
            continue
        visited[s] = True
        cnt = 0
        for v in edge[s]:
            if visited[v]:
                continue
            ans *= color - 1 - cnt
            ans %= MOD
            cnt += 1
            q.append([v,K-1])

    print(ans)

    



if __name__ == "__main__":
    main()

Solution (Python):
import sys
sys.setrecursionlimit(1000000000)
input = sys.stdin.readline
N, K = map(int, input().split())
graph = [[] for _ in range(N)]
for _ in range(N-1):
  a, b = map(lambda x:int(x)-1, input().split())
  graph[a] += [b]
  graph[b] += [a]

global ans
ans = K

def npr(n, r, p):
  e = 1
  for i in range(n, n-r, -1):
    e *= i
    e %= p

  return e
p=10**9+7

def dfs(u, pre):
  global ans
  child = 0
  for v in graph[u]:
    if v != pre:
      dfs(v, u)
      child += 1
  
  if u == 0:
    ans *= npr(K-1, child, p)
  else:
    ans *= npr(K-2, child, p)

  ans %= p

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

Solution (Python):
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

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

    q = collections.deque()
    q.append((0,K))
    node = [0] * N
    node[0] = 1
    ans = 1
    while q:
        v,c = q.popleft()
        ans = (ans * c) % MOD
        if c < K: c = K-1
        for u in root[v]:
            if node[u] > 0: continue
            c -= 1
            q.append((u,c))
            node[u] = 1
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import Counter
input = sys.stdin.readline
N, K = map(int, input().split())
mod = 10 ** 9 + 7
e = [[] for _ in range(N + 1)]
for _ in range(N - 1):
  u, v = map(int, input().split())
  e[u].append(v)
  e[v].append(u)
if N == 1:
  print(K)
  exit(0)
elif N == 2:
  print(K * (K - 1))
  exit(0)
s = [1]
vis = [0] * (N + 1)
order = []
parent = [0] * (N + 1)
children = [0] * (N + 1)
while len(s):
  x = s.pop()
  vis[x] = 1
  order.append(x)
  for y in e[x]:
    if vis[y]: continue
    s.append(y)
    parent[y] = x
    children[x] += 1
cs = Counter()
cr = children[1]
for y in range(2, N + 1): cs[children[y]] += 1

res = [0] * (K + 1)
l = 0
csmx = 0
if len(cs): csmx = max(cs.keys())

for c in range(K + 1):
  if c <= 1 and (cr > 0): continue
  if c <= 2 and (len(cs) > 0): continue
  if c - 1 >= cr and (c - 2 >= csmx):
    l = c
    break
if l == 0:
  print(0)
  exit(0)

class Factorial:
  def __init__(self, n, 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] % mod * self.i[k] % mod

f = Factorial(K, mod)
smcs = sum(cs.values())
res[l] = f.factorial(l) * f.ifactorial(l - cr - 1) % mod
for k, v in cs.items():
  res[l] *= pow(f.factorial(l - 2) * f.ifactorial(l - k - 2) % mod, v, mod)
  res[l] %= mod

revs = [0] * (K + 1)
for i in range(K + 1): revs[i] = pow(i, mod - 2, mod)
for i in range(l, K):
  res[i + 1] = res[i] * pow(i - 1, smcs, mod) % mod
  res[i + 1] *= (i + 1) * revs[i - cr] % mod
  res[i + 1] %= mod
  for k, v in cs.items():
    res[i + 1] *= pow(revs[i - k - 1], v, mod)
    res[i + 1] %= mod

print(res[-1])

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

import sys
sys.setrecursionlimit(10**9)
edge = [[] for _ in range(N)]
for u,v in AB:
    edge[u-1].append(v-1)
    edge[v-1].append(u-1)

MOD = 10**9+7
mod = 10 ** 9 + 7
MAX = K+10
fac = [0] * MAX
finv = [0] * MAX
inv = [0] * MAX
def cominit():
    fac[0] = 1
    fac[1] = 1
    finv[0] = 1
    finv[1] = 1
    inv[1] = 1
    for i in range(2,MAX):
        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 cmb(n,r):
    if n < 0 or r < 0 or r > n:return 0
    if r > n/2: r = n-r        
    return fac[n] * (finv[r] * finv[n-r] % mod) % mod

def permu(n,r):
    if n<=0 or r<=0 or r>n: return 0
    return (fac[n]*finv[n-r])%MOD
cominit()



visited = [False]*N
visited[0] = True
def dfs(s,ans):
    M = len(edge[s])-1*(s!=0)
    if M==0:
        return ans
    if s==0:
        ans *= permu(K-1, M)
        ans %= MOD
    else:
        ans *= permu(K-2, M)
        ans %= MOD

    for nv in edge[s]:
        if visited[nv]:continue
        visited[nv] = True
        ans = dfs(nv, ans)
    
    return ans

print(dfs(0,K)%MOD)

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

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

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

ab = [tuple(map(int,input().split())) for i in range(n-1)]
p=10**9+7
es = [[] for i in range(n)]
for i, (a,b) in enumerate(ab):
    a,b = a-1,b-1
    es[a].append(b)
    es[b].append(a)

d = [1]*n
for i in range(1,n):
    d[i] *= d[i-1]*max(0,(k-1-i))%p
    d[i] %=p

root=0
ans = k
for i in range(n):
    if i == root:
        ans *= (k-1)*d[len(es[i])-1]%p
    else:
        ans *= d[len(es[i])-1]%p

print(ans%p)

Solution (Python):




N,K = map(int, input().split())
es = [[] for _ in range(N)]

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


MOD = 10**9+7
 
MAXN = K+5
fac = [1,1] + [0]*MAXN
finv = [1,1] + [0]*MAXN
inv = [0,1] + [0]*MAXN
for i in range(2,MAXN+2):
    fac[i] = fac[i-1] * i % MOD
    inv[i] = -inv[MOD%i] * (MOD // i) % MOD
    finv[i] = finv[i-1] * inv[i] % MOD
 
def nPr(n,r):
    if n < r:
        return 0
    return fac[n] * finv[n-r]

ans = 1

checked = [False] * N
q = []

ans *= K * nPr(K-1, len(es[0]))

checked[0] = True
for nxt in es[0]:
    q.append(nxt)
    checked[nxt] = True

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

Solution (Python):
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())
    g[a - 1].append(b - 1)
    g[b - 1].append(a - 1)
s = [0]
d = [-1] * n
while s:
    p = s.pop()
    if d[p] == -1:
        s.append(p)
        d[p] = -2
        for node in g[p]:
            if d[node] == -1:
                s.append(node)
    else:
        res = 1
        if s:
            t = k - 2
        else:
            t = k - 1
        f = 1
        for node in g[p]:
            if d[node] != -2:
                f *= t
                f %= MOD
                t -= 1
                res *= d[node]
                res %= MOD
        d[p] = res * f
print(d[0] * k % MOD)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
mod = 10**9+7
sys.setrecursionlimit(4100000)
n,k = map(int,readline().split())
if n == 1:
  print(k%mod)
  exit()

g = [[] * n for i in range(n)]
for i in range(n-1):
    u, v = map(int,readline().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)

ans = 1
used = [False]*n
def dfs(now,prev,p):
    global ans
    if k <= p:
      ans = 0
    ans *= k-p
    ans %= mod
    used[now] == True
    if all(used):
      return ans
    cnt = 1
    new = []
    for next in g[now]:
      if next == prev:
        cnt += 1
      else:
        new.append(next)
    for i,next in enumerate(new):
      dfs(next,now,cnt+i)
      
dfs(0,-1,0)
print(ans)

Solution (Python):

import sys
from collections import defaultdict



sys.setrecursionlimit(10 ** 7)
INF = float("inf")
MOD = 10 ** 9 + 7


def combination(n, k):
    if k > n - k:
        return combination(n, n - k)
    return fact[n] * ifact[k] * ifact[n - k]


def permitation(n, k):
    
    res = combination(n, k) * fact[k]
    return res % MOD


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


n = 200005
fact = defaultdict(int)
fact[0] = 1
for i in range(1, n + 1):
    fact[i] = fact[i - 1] * i
    fact[i] %= MOD

ifact = defaultdict(int)
ifact[n] = pow(fact[n], MOD - 2, MOD)
for i in reversed(range(1, n + 1)):
    ifact[i - 1] = ifact[i] * i
    ifact[i - 1] %= MOD


def dfs(v, p=-1):
    global ans
    for u in to[v]:
        if u == p:
            continue
        dfs(u, v)
    if p == -1:
        nk = K
        c = len(to[v]) + 1
    else:
        nk = K - 2
        c = len(to[v]) - 1
    ans *= permitation(nk, c)
    ans %= MOD


ans = 1
dfs(0)
print(ans)

Solution (Python):
import sys
from collections import defaultdict



sys.setrecursionlimit(10 ** 7)
INF = float("inf")
MOD = 10 ** 9 + 7


def combination(n, k):
    if k > n - k:
        return combination(n, n - k)
    return fact[n] * ifact[k] * ifact[n - k]


def permitation(n, k):
    
    if n < 0:
        return 0
    res = combination(n, k) * fact[k]
    return res % MOD


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


n = 200005
fact = defaultdict(int)
fact[0] = 1
for i in range(1, n + 1):
    fact[i] = fact[i - 1] * i
    fact[i] %= MOD

ifact = defaultdict(int)
ifact[n] = pow(fact[n], MOD - 2, MOD)
for i in reversed(range(1, n + 1)):
    ifact[i - 1] = ifact[i] * i
    ifact[i - 1] %= MOD


def dfs(v, p=-1):
    global ans
    for u in to[v]:
        if u == p:
            continue
        dfs(u, v)
    if p == -1:
        nk = K
        c = len(to[v]) + 1
    else:
        nk = K - 2
        c = len(to[v]) - 1
    ans *= permitation(nk, c)
    ans %= MOD


ans = 1
dfs(0)
print(ans)

Solution (Python):
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  

sys.setrecursionlimit(100005)

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

mod = 10**9 + 7


def dfs(cur, par, k, g):
    ret = 1
    nc = 0 if par == -1 else 1
    for e in g[cur]:
        if e == par: continue
        nc += 1
        ret = ret * (k - nc) % mod
        ret = ret * dfs(e, cur, k, g) % mod
    return ret % mod


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

Solution (Python):

import sys
input = sys.stdin.readline




class Modinv:
    def __init__(self, n, mod):
        self.mod = mod
        self.fact = [1]*n
        self.finv = [1]*n
        self.inv  = [1]*n
        for i in range(2,n):
            self.fact[i] = (self.fact[i-1]*i) % self.mod
            self.inv[i]  = self.mod - self.inv[self.mod%i] * (self.mod//i)%self.mod
            self.finv[i] = self.finv[i-1] * self.inv[i] % self.mod
 
    def nCr(self, n, r):
        if n<r:
            return 0
        else:
            return self.fact[n] * (self.finv[r] * self.finv[n-r] % self.mod) % self.mod
    
    def nPr(self, n, r):
        if n<r:
            return 0
        else:
            return self.fact[n] * self.finv[n-r] % self.mod

mod = 10**9+7




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

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

Modinv = Modinv(K+10, mod)


ans = K

from collections import deque
dq = deque([(0,0)]) 
visited = [False]*N 

while dq:
    v,d = dq.pop()
    visited[v] = True
    cnt = 0 
    for e in A[v]:
        if visited[e]:
            continue
        cnt += 1
        dq.append((e, d+1))
    
    if cnt==0:
        continue
    
    if d==0:
        n = Modinv.nPr(K-1,cnt)
    
    else:
        n = Modinv.nPr(K-2,cnt)
    
    ans *= n
    ans %= mod

print(ans)

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

mod = 10 ** 9 + 7

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)

ans = K

def factorial(n, k, mod):
    fact = 1
    for integer in range(n, n-k, -1):
        fact *= integer
        fact %= mod
    return fact

def dfs(parent, current):
    ret = 1
    for child in graph[current]:
        if child != parent:
            ret *= dfs(current, child)
    L = len(graph[current])
    R = K - 1
    if parent != -1:
        L -= 1
        R -= 1
    ret *= factorial(R, L, mod)
    return ret % mod

ans *= dfs(-1, 0)
ans %= mod

print(ans)

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

num = 100010
fact = [1] * (num+1)
ifact = [1] * (num+1)
inv = [pow(i,MOD-2,MOD) for i in range(num+1)]
for i in range(1,num+1):
    fact[i] = (fact[i-1] * i) % MOD
    ifact[i] = (ifact[i-1] * inv[i]) % MOD

def nPr(n,r):
    return (fact[n] * ifact[n-r]) % MOD

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

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

dq = deque([1])

visited = [False] * (N+1)

ans = nPr(K,len(g[1])+1)
while dq:
    v = dq.popleft()
    visited[v] = True
    if v != 1:
        npattern = len(g[v])-1
        ans *= nPr(K-2,npattern)
        ans %= MOD
    for nv in g[v]:
        if visited[nv]:
            continue
        dq.append(nv)
print(ans)

Solution (Python):


import sys




from collections import deque                
















def main():
    mod = 1000000007                
    inf = float('inf')              
    inf = 2 ** 64 - 1               
    sys.setrecursionlimit(10**6)    
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())

    
    n, k = mi()
    
    adj = [[] for _ in range(n)]  
    for _ in range(n - 1):
        a, b = mi_0()
        adj[a].append(b)
        adj[b].append(a)
    
    
    tree_parent_ind = [None] * n
    tree_children_indices = [[] for _ in range(n)]
    root = 0
    stack = [[root, None]]
    while stack:
        u, prev = stack.pop()
        tree_parent_ind[u] = prev
        for v in adj[u]:
            if v != prev:
                tree_children_indices[u].append(v)
                stack.append([v, u])

    def calc_possible_colors(ind, k):
        determined_colors = 0
        p = tree_parent_ind[ind]
        if p is not None:
            determined_colors += 1
            determined_colors += tree_inserted_children_num[p]
            if tree_parent_ind[p] is not None:
                determined_colors += 1
        return max(k - determined_colors, 0)
            
    
    tree_inserted_children_num = [0] * n
    def calc_cases_bfs(start):
        cases = 1
        q = deque([start])
        while q:
            u = q.popleft()
            possible_colors = calc_possible_colors(u, k)
            if possible_colors == 0:
                return 0
            cases = (cases * possible_colors) % mod
            
            if tree_parent_ind[u] is not None:
                tree_inserted_children_num[tree_parent_ind[u]] += 1
            for child in tree_children_indices[u]:
                q.append(child)
        return cases

    print(calc_cases_bfs(root))


if __name__ == "__main__":
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
MOD=10**9+7
def facinv(N):
    fac,finv,inv=[0]*(N+1),[0]*(N+1),[0]*(N+1)
    fac[0]=1;fac[1]=1;finv[0]=1;finv[1]=1;inv[1]=1
    for i in range(2,N+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
    return fac,finv,inv

def PER(n,r):
    if n<r or r<0:
        return 0
    else:
        return (fac[n]*finv[n-r])

def dfs(v,p,dep):
    global res
    c=0
    for nv in G[v]:
        if nv==p:
            continue
        dfs(nv,v,dep+1)
        c+=1
    if dep==0:
        res=(res*PER(K-1,c)%MOD)
    else:
        res=(res*PER(K-2,c)%MOD)
    
N,K=map(int,input().split())
G=[[] for i in range(N)]
for i in range(N-1):
    a,b=map(lambda x:int(x)-1,input().split())
    G[a].append(b)
    G[b].append(a)
fac,finv,inv=facinv(max(K,N))
res=K
dfs(0,-1,0)
print(res%MOD)

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
MOD=10**9+7
def facinv(N):
    fac,finv,inv=[0]*(N+1),[0]*(N+1),[0]*(N+1)
    fac[0]=1;fac[1]=1;finv[0]=1;finv[1]=1;inv[1]=1
    for i in range(2,N+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
    return fac,finv,inv

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

def dfs(v,p,dep):
    global res
    c=0
    for nv in G[v]:
        if nv==p:
            continue
        dfs(nv,v,dep+1)
        c+=1
    if dep==0:
        res=((res*COM(K-1,c)%MOD)*fac[c])%MOD
    else:
        res=((res*COM(K-2,c)%MOD)*fac[c])%MOD
    
N,K=map(int,input().split())
G=[[] for i in range(N)]
for i in range(N-1):
    a,b=map(lambda x:int(x)-1,input().split())
    G[a].append(b)
    G[b].append(a)
fac,finv,inv=facinv(max(K,N))
res=K
dfs(0,-1,0)
print(res%MOD)

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


def dfs(K, u, p):
    if p == -1:
        can_use_color_num = K - 1
    else:
        can_use_color_num = K - 2

    
    
    
    case_num = 1
    for e in edges[u]:
        if e == p:
            continue
        case_num *= can_use_color_num
        can_use_color_num -= 1
        case_num %= mod
    for e in edges[u]:
        if e == p:
            continue
        case_num *= dfs(K, e, u)
        case_num %= mod
    return case_num

ans = K * dfs(K, 0, -1)
ans %= mod
print(ans)

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

MOD = 10**9 + 7

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

nums = [1] * N
def dfs(vNow, vPar):
    numCh = 0
    for v2 in adjL[vNow]:
        if v2 == vPar: continue
        dfs(v2, vNow)
        numCh += 1
    num = 1
    if vPar == -1:
        for i in range(K-numCh, K):
            num *= i
            num %= MOD
    else:
        for i in range(K-numCh-1, K-1):
            num *= i
            num %= MOD
    nums[vNow] = num

dfs(0, -1)

ans = K
for num in nums:
    ans *= num
    ans %= MOD

print(ans)

Solution (Python):
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
n, k = map(int, readline().split())


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

mod = 10 ** 9 + 7
kaidan = [1] * (10 ** 5 + 1)
gyaku = [1] * (10 ** 5 + 1)

for i in range(1, 10 ** 5 + 1):
    kaidan[i] = i * kaidan[i - 1] % mod
    gyaku[i] = pow(kaidan[i], mod - 2, mod)


def perm(k, i):
    if i > k:
        return 0
    return kaidan[k] * gyaku[k - i]




stack = [1]
used = [False] * (n + 1)
while stack:
    v = stack.pop()
    used[v] = True
    if v == 1:
        ans *= k * perm(k - 1, cnt[v])
        ans %= mod
    else:
        ans *= perm(k - 2, cnt[v] - 1)
        ans %= mod
    for u in graph[v]:
        if used[u] == True:
            continue
        stack.append(u)

print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(100000000)
N, K = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(N-1)]
graph = [[] for _ in range(N)]
used = [-1]*N
ans = K
mod = 10**9+7

for a, b in ab:
  a -= 1
  b -= 1
  graph[a] += [b]
  graph[b] += [a]


def npr(n, r, p):
  e = 1
  for i in range(n, n-r, -1):
    e *= i
    e %= p

  return e

def dfs(u, pre):
  global ans
  child = 0
  for v in graph[u]:
    if v != pre:
      dfs(v, u)
      child += 1
  if u == 0:
    ans *= npr(K-1, child, mod)
  else:
    ans *= npr(K-2, child, mod)

  ans %= mod

dfs(0, -1)
print(ans)

Solution (Python):

import sys
from collections import deque
N,K=map(int, sys.stdin.readline().split())

al=[ [] for _ in range(N+1) ]	
for _ in range(N-1):
    a,b=map(int, sys.stdin.readline().split())
    al[a].append(b)
    al[b].append(a)
   
mod=10**9+7
ans=1


start=1
Visit=[ 0 for _ in range(N+1) ] 
q=deque()
q.append((start,K)) 
Visit[start]=1

while q:
    fro,k=q.pop()
    ans*=k  
    ans%=mod
    if fro==1:  
        num=K-1
    else:       
        num=K-2  
    for to in al[fro]:
        if Visit[to]==0:
            Visit[to]=1	
            q.append((to,num))
            num-=1
print ans

Solution (Python):

import sys
from collections import deque
N,K=map(int, sys.stdin.readline().split())

al=[ [] for _ in range(N+1) ]	
for _ in range(N-1):
    a,b=map(int, sys.stdin.readline().split())
    al[a].append(b)
    al[b].append(a)
   
mod=10**9+7
ans=1


start=1
Visit=[ 0 for _ in range(N+1) ] 
q=deque()
q.append((start,K)) 
Visit[start]=1

while q:
    fro,k=q.pop()
    ans*=k  
    ans%=mod
    if fro==1:  
        num=K-1
    else:       
        num=K-2  
    for to in al[fro]:
        if Visit[to]==0:
            Visit[to]=1	
            q.append((to,num))
            num-=1
print ans

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