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 deque

def permutation(n, k):
    s = 1
    for _ in range(k):
        s *= n
        s %= mod
        n -= 1
    return s

def bfs():
    global ans
    q = deque()
    q.append([1, 0])
    visit[1] = 1
    while q:
        x, y = q.popleft()
        a = 0
        for i in T[x]:
            if visit[i] == 0:
                q.append([i, 1])
                visit[i] = 1
                a += 1
        b = k - y - 1
        if b - a < 0:
            print(0)
            exit()
        ans *= permutation(b, a)
        ans %= mod
    return 

n, k = map(int, input().split())
T = [[] for _ in range(n + 1)]
visit = [0] * (n + 1)
mod = pow(10, 9) + 7
for _ in range(n - 1):
    a, b = map(int, input().split())
    T[a].append(b)
    T[b].append(a)
ans = k
bfs()
print(ans)

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

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)

MAX=10**6
fc=[1]*MAX
inv=[1]*MAX
ifc=[1]*MAX

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

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

def dfs(cur,par):
    ret=1
    ch=len(g[cur])
    if par!=-1:
        ch-=1
    
    if par==-1:
        ret=comb(K-1,ch)*fc[ch]%MOD
    else:
        ret=comb(K-2,ch)*fc[ch]%MOD
        
        
    for dst in g[cur]:
        if dst==par:
            continue
        ret=ret*dfs(dst,cur)%MOD
    return ret

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

Solution (Python):
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, K, *AB = map(int, read().split())
    G = [[] for _ in range(N)]
    for a, b in zip(AB[::2], AB[1::2]):
        G[a - 1].append(b - 1)
        G[b - 1].append(a - 1)

    COM_MAX = K

    fac, finv, inv = [0] * (COM_MAX + 1), [0] * (COM_MAX + 1), [0] * (COM_MAX + 1)
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1

    for i in range(2, COM_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 mod_perm(n, r):
        if n < r:
            return 0
        if n < 0 or r < 0:
            return 0
        return fac[n] * (finv[n - r] % MOD) % MOD

    stack = deque([0])
    order = []
    parent = [-1] * N
    while stack:
        v = stack.pop()
        order.append(v)
        for nv in G[v]:
            if nv != parent[v]:
                stack.append(nv)
                parent[nv] = v

    A = [0] * N
    for v in reversed(order):
        tmp = 1
        child = 0
        for nv in G[v]:
            if nv != parent[v]:
                tmp = tmp * A[nv] % MOD
                child += 1

        colors = K if v == 0 else K - 2
        nodes = child + 1 if v == 0 else child

        A[v] = tmp * mod_perm(colors, nodes) % MOD

    print(A[0])
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, K, *AB = map(int, read().split())
    G = [[] for _ in range(N)]
    for a, b in zip(AB[::2], AB[1::2]):
        G[a - 1].append(b - 1)
        G[b - 1].append(a - 1)

    COM_MAX = K

    fac, finv, inv = [0] * (COM_MAX + 1), [0] * (COM_MAX + 1), [0] * (COM_MAX + 1)
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1

    for i in range(2, COM_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 mod_perm(n, r):
        if n < r:
            return 0
        if n < 0 or r < 0:
            return 0
        return fac[n] * (finv[n - r] % MOD) % MOD

    stack = deque([0])
    order = []
    parent = [-1] * N
    while stack:
        v = stack.pop()
        order.append(v)
        for nv in G[v]:
            if nv != parent[v]:
                stack.append(nv)
                parent[nv] = v

    A = [0] * N
    for v in reversed(order):
        tmp = 1
        child = 0
        for nv in G[v]:
            if nv != parent[v]:
                tmp = tmp * A[nv] % MOD
                child += 1

        colors = K if v == 0 else K - 2
        nodes = child + 1 if v == 0 else child

        A[v] = tmp * mod_perm(colors, nodes) % MOD

    print(A[0])
    return


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
import bisect
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()

class Counting():
    def __init__(self,maxim,mod):
        maxim += 1

        self.mod = mod
        self.fact = [0]*maxim
        self.fact[0] = 1
        for i in range(1,maxim):
            self.fact[i] = self.fact[i-1] * i % mod

        self.invfact = [0]*maxim
        self.invfact[maxim-1] = pow(self.fact[maxim-1],mod-2,mod)
        for i in reversed(range(maxim-1)):
            self.invfact[i] = self.invfact[i+1] * (i+1) % mod


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

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


def main():
    N,K=mi()
    graph = [[] for _ in range(N+1)]
    MOD = 10**9+7

    a = 0
    for i in range(N-1):
        a,b=mi()
        graph[a].append(b)
        graph[b].append(a)

    stack = deque([(a,1)])
    seen = set()

    counting = Counting(K+10,MOD)
    ans = counting.nPk(K,1)

    def _len(X):
        cnt = 0
        for x in X:
            if x in seen: continue
            cnt += 1
        
        return cnt

    while len(stack) > 0:
        next,depth = stack.popleft()
        seen.add(next)
        

        if depth == 1:
            ans *= counting.nPk(K-1,_len(graph[next]))
            ans %= MOD
            
            
        
        else:
            ans *= counting.nPk(K-2,_len(graph[next]))
            
            
            ans %= MOD


        for g in graph[next]:
            if g in seen: continue
            stack.append((g,depth+1))


    print(ans%MOD)



if __name__ == "__main__":
  main()

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

MOD = 10**9 + 7
n, k = map(int, input().split())
graph = [[] for _ in range(n)]
k_inv = pow(k, MOD - 2, MOD)
for _ in range(n - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)


def dfs(v, v_p):
    
    if v_p == -1:  
        c = k - 1
    else:
        c = k - 2

    cnt = 1
    i = 0
    for v_next in graph[v]:
        if v_next == v_p:
            continue
        cnt *= max(0, c - i)
        cnt %= MOD
        cnt *= dfs(v_next, v)
        cnt %= MOD
        i += 1
    return cnt


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

Solution (Python):
import networkx as nx

int1 = lambda x: int(x) - 1
MOD = 10 ** 9 + 7

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

G = nx.Graph()
G.add_nodes_from(range(N))
G.add_edges_from([tuple(map(int1, input().split())) for _ in range(N - 1)])

deg = nx.degree(G)
ans = K
for i in range(deg[0]):
    ans = (ans * (K - i - 1)) % MOD

for parent, child in nx.dfs_edges(G, 0):
    for i in range(deg[child] - 1):
        ans = (ans * (K - i - 2)) % MOD

print(ans)

Solution (Python):
import networkx as nx

int1 = lambda x: int(x) - 1
MOD = 10 ** 9 + 7

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

G = nx.Graph()
G.add_nodes_from(range(N))
G.add_edges_from([tuple(map(int1, input().split())) for _ in range(N - 1)])

ans = K
for i in range(nx.degree(G)[0]):
    ans = (ans * (K - i - 1)) % MOD

for parent, child in nx.dfs_edges(G, 0):
    for i in range(nx.degree(G)[child] - 1):
        ans = (ans * (K - i - 2)) % MOD

print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10000000)
n,k=map(int,input().split())
CONST=10**9+7
path={i:list() for i in range(n)}
for i in range(n-1):
  a,b=map(int,input().split())
  path[a-1].append(b-1)
  path[b-1].append(a-1)
used=[0]*n
used[0]=1
  
def bfs(pos, parent):
  res=k-parent
  if parent>0:
    deg=2
  else:
    deg=1
  for nex in path[pos]:
    if used[nex]:
      continue
    used[nex]=1
    res *= bfs(nex,deg)
    res = res%CONST
    deg += 1
  return res%CONST
    
print(bfs(0, 0))

Solution (Python):
def main():
  MOD =  10**9 + 7
  N, K = map(int, input().split())
  ki = [[] for _ 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)
  d = [-1] * N
  que = []
  ans = K
  d[0] = 1
  for i, nex in enumerate(ki[0]):
    d[nex] = 1
    ans *= (K-i-1)
    ans %= MOD
    que.append(nex)
  while len(que) > 0:
    now = que.pop(0)
    count = 2
    for nex in ki[now]:
      if d[nex] != -1:
        continue
      d[nex] = 1
      ans *= (K-count)
      count += 1
      ans %= MOD
      que.append(nex)
  print(ans)
  
if __name__ == "__main__":
  main()

Solution (Python):
import sys
def input():return sys.stdin.readline().strip()

from collections import deque


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

    MAX_N = 3 * 10 ** 5
    MOD = 10 ** 9 + 7
    fac = [0]*MAX_N
    inv = [0]*MAX_N
    finv = [0]*MAX_N
    fac[0] = 1; fac[1] = 1
    inv[1] = 1
    finv[0] = 1; finv[1] = 1

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

    def perm(n, r):
        if n < 0:return 0
        elif r > n: return 0
        
        return fac[n]*finv[n-r]%MOD
    
    
    com_init()
    def dfs(s):
        stack = deque()
        stack.append((s, -1)) 
        res = K
        while stack:
            now, par = stack.pop()

            if now == 0:
                children = len(to[now])
            else:
                children = len(to[now]) - 1

            if now == 0:
                nx_col = K - 1
            else:
                nx_col = K - 2
            
            res *= perm(nx_col, children)
            res %= MOD

            if children == 0 and now != 0:
                continue
            
            for nv in to[now]:
                if nv != par:
                    stack.append((nv, now))
        return res
    ans = dfs(0)
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
n,k = map(int,input().split())
li = [[] for _ in range(n+1)]
mod = 10**9+7
ans = k
perm = [1]*(n)

for i in range(n-1):
    a,b = map(int,input().split())
    li[a].append(b)
    li[b].append(a)
    perm[i+1] = (perm[i]*(k-2-i))%mod

def dfs(now,before):
    point = 1
    if now == 1:
        ret = 1
        ko = len(li[1])
        for i in range(ko):
            ret *= k-1-i
            ret %= mod
    else:
        ko = len(li[now])-1
        ret= perm[ko]%mod
    
    for i in li[now]:
        if i==before:
            continue
        ret = ret*dfs(i,now)%mod
    return ret

ans *= dfs(1,0)

print(ans%mod)

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


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

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

    ans = K
    q = deque([1])
    used = [False]*(N+1)
    used[1] = True

    while q:
        s = q.popleft()
        pos = 1 if s==1 else 2
        for t in d[s]:
            if used[t]:continue
            used[t] = True
            ans *= (K-pos)
            ans %= MOD
            pos += 1
            q.append(t)

    print(ans)


if __name__ == "__main__":
    solve()

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


def solve():
    N, K = map(int, input().split())
    d = defaultdict(list)
    MOD = 10**9+7

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

    ans = K
    used = [0]*(N+1)
    used[1] = True
    q = deque([1])

    while q:
        a = q.popleft()
        s = 1 if a==1 else 2
        for b in d[a]:
            if used[b]:continue
            used[b] = True
            ans *= (K-s)
            s += 1
            q.append(b)
            ans %= MOD
    print(ans)

solve()

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
def main():
    N, K = map(int, readline().split())
    to = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b = map(int, readline().split())
        a-=1
        b-=1
        to[a].append(b)
        to[b].append(a)

    P = int(1e9)+7
    
    
    
    
    
    
    
    

    
    from collections import deque 
    dq = deque()
    
    dq.append(0)
    
    ans = K%P
    done = [0 for _ in range(N)]
    done[0] = 1
    
    while len(dq)>0:
        v = dq.popleft()
        i = 2
        if v == 0:
            i = 1
        for nx in to[v]:
            if done[nx] == 1:
                continue
            if K-i<=0:
                print(0)
                return
            ans *= K-i
            ans %= P
            i += 1
            done[nx] = 1
            dq.append(nx)

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

Solution (Python):
from collections import deque
import sys

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

T = [[] 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)

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

def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

if K - len(T[0]) - 1 < 0:
    print(0)
    sys.exit()

ans = fac[K] * modinv(fac[K - len(T[0]) - 1])
q = deque(T[0])
used = [0]*N
used[0] = 1
for i in T[0]:
    used[i] = 1

while(len(q)>0):
    a = q.popleft()
    if len(T[a]) != 1:
        if K - len(T[a]) - 1 < 0:
            print(0)
            sys.exit()
        ans *= fac[K-2]*modinv(fac[K - len(T[a]) - 1])
        ans %= mod
    for i in T[a]:
        if used[i] == 0:
            q.append(i)
            used[i] = 1
print(ans%mod)

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

adj = [[] for _ in range(n + 1)]
for a, b in ab:
    adj[a].append(b)
    adj[b].append(a)

s = 1
p = [-1] * (n + 1)
p[0] = 0
p[1] = 0
c = [[] for _ in range(n + 1)]
order = []
stack = [s]
while stack:
    u = stack.pop()
    order.append(u)
    for v in adj[u]:
        if p[v] == -1:
            p[v] = u
            c[u].append(v)
            stack.append(v)

ans = k
for u in order:
    mx = k - 1
    par = p[u]
    if par:
        mx -= 1

    for i in range(len(c[u])):
        ans *= mx - i
        ans %= mod

print(ans)

Solution (Python):

import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

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

MOD = 10 ** 9 + 7

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

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

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

U = 10 ** 6  
fact, fact_inv = make_fact(U, MOD)


answer = 1
root = 1
parent = [0] * (N+1)
order = []
stack = [root]
answer = K * perm(K-1, len(graph[root])) % MOD
while stack:
    cur = stack.pop()
    order.append(cur)
    if cur != 1:
        answer *= perm(K-2, len(graph[cur])-1)
        answer %= MOD
    for next in graph[cur]:
        if next == parent[cur]:
            continue
        parent[next] = cur
        stack.append(next)

print(answer%MOD)

Solution (Python):
from collections import deque


def create_factorial(n):
    """
    階乗を事前計算した配列を作成します。
    :param n: [0, n]の配列を作成します
    """
    f = list()
    for i in range(n + 1):
        if i in [0, 1]:
            f.append(1)
        else:
            f.append(f[i - 1] * i % MOD)
    return f


MOD = 10 ** 9 + 7

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

ans = K
q = deque()
q.append((0, -1))
while len(q) > 0:
    v, p = q.popleft()
    c = 0
    for nxt in adj[v]:
        if nxt != p:
            q.append((nxt, v))
            c += 1
    n = K - 1 if p == -1 else K - 2
    r = n - c
    if c > n:
        print(0)
        exit()
    ans = ans * (f[n] % MOD) * pow(f[r], MOD - 2, MOD) % MOD

print(ans)

Solution (Python):
from collections import deque, Counter

N,K,*abf = map(int, open(0).read().split())
ab = [abf[i:i+2] for i in range(0, len(abf), 2)]
connected = [[] for _ in range(N+1)]
m = 1000000007
for a, b in ab:
    connected[a].append(b)
    connected[b].append(a)
    
dist = [-1] * (N+1)
d = deque([1])
parents = [-1] * (N+1)
dist[1] = 0
while d:
    temp = d.popleft()
    for edge in connected[temp]:
        if dist[edge] == -1:
            d.append(edge)
            dist[edge] = dist[temp] + 1
            parents[edge] = temp
ans = K
c = Counter(parents)
for x in c.items():
    if x[0] < 1:
        continue
    elif x[0] == 1:
        for i in range(1,x[1]+1):
            ans = (ans*(K-i)) % m
    else:
        for i in range(2,x[1]+2):
            ans = (ans*(K-i)) % m
print(ans)

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

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

T = [[] for i 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)

ans = 1
def dfs(i, bb, b, p):
    global ans
    ans = (ans*(K-bb-b))%(10**9+7)
    cnt = 0
    for j in T[i]:
        if j == p:
            continue
        dfs(j, b + cnt, 1, i)
        cnt += 1

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

Solution (Python):
n,k = map(int,input().split())
if n == 1:
    print(k)
else:
    edges = {}
    for i in range(n-1):
        a,b = map(int,input().split())
        if a not in edges:
            edges[a] = [b]
        else:
            edges[a].append(b)

        if b not in edges:
            edges[b] = [a]
        else:
            edges[b].append(a)

    now = set([1])
    visited = set([1])
    goal = -1
    flag = False
    ans = k
    mod = 10**9+7
    while True:
        buf = set()
        if len(now) == 0:
            break
        for n in now:
            if n == 1:
                for i in range(len(edges[n])):
                    ans *= k-1-i
                    ans %= mod
                for nn in edges[n]:
                    if nn in visited:
                        continue
                    else:
                        buf.add(nn)
                        visited.add(nn)

            else:
                temp = 0
                for nn in edges[n]:
                    if nn in visited:
                        continue
                    else:
                        temp += 1
                        buf.add(nn)
                        visited.add(nn)
                for i in range(temp):
                    ans *= k - 2 - i
                    ans %= mod
        
        
        now = buf
    
    print(ans%mod)

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 6)
N,K=map(int,input().split())
tree=[[]for _ in range(N+1)]
MOD=10**9+7
ans=K
enuk=[1]*(N)
for i in range(N-1):
    a,b=map(int,input().split())
    tree[a].append(b)
    tree[b].append(a)
    enuk[i+1]=(enuk[i]*(K-2-i))%MOD
def dfs(a,b):
    if a==1:
        node=len(tree[a])
        ret=1
        for i in range(node):
            ret*=K-1-i
            ret%=MOD
    else:
        node=len(tree[a])-1
        ret=enuk[node]%MOD
    for i in tree[a]:
        if i==b:
            continue
        ret=ret*dfs(i,a)%MOD
    return ret
ans*=dfs(1,0)
print(ans%MOD)

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

n, k = map(int, input().split())
edge = [[] for _ in range(n)]
parent = [0] * n
permutation_k2 = [1] * 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)
  permutation_k2[i+1] = permutation_k2[i] * (k - 2 - i) % mod
count = k * (k - 1) * permutation_k2[len(edge[0]) - 1] % mod
queue = edge[0]
while queue:
  vertex = queue.pop()
  count = count * permutation_k2[len(edge[vertex]) - 1] % mod
  p = parent[vertex]
  for v in edge[vertex]:
    if v == p:
      continue
    queue.append(v)
    parent[v] = vertex
if n == 1:
  print(k)
else:
  print(count)

Solution (Python):
import sys
sys.setrecursionlimit(1000000000)
n,k = map(int,input().split())
G = [[] for _ in range(n)]
for _ in range(n-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)

mod = 1000000007
def perm(n,k):
    if n < k: return 0
    if n < 0 or k < 0: return 0
    return fac[n]*finv[n-k]%mod
fac = [1]*(k+1)
finv = [1]*(k+1)
for i in range(1,k+1):
    fac[i] = fac[i-1]*i%mod
    finv[i] = pow(fac[i],mod-2,mod)

def dfs(cur,prev=-1):
    nxtcnt = 0
    res = 1
    for nxt in G[cur]:
        if nxt == prev: continue
        nxtcnt += 1
        res = res*dfs(nxt,cur)%mod
    colors = k-1 if cur == 0 else k-2
    res = res*perm(colors,nxtcnt)%mod
    return res
  
ans = k*dfs(0)%mod
print(ans)

Solution (Python):
from collections import defaultdict
from collections import deque
import sys
sys.setrecursionlimit(10**6)

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

MOD = 10**9+7


def dfs(v, pv, n):
    k = K-1 if pv == -1 else K-2
    a = 1
    for u in ab[v]:
        if u != pv:
            a *= dfs(u, v, k)
            a %= MOD
            k -= 1
    return a*n % MOD


print(dfs(0, -1, K))

Solution (Python):
class Cmb:
    def __init__(self, N, mod=10**9+7):
        self.fact = [1,1]
        self.fact_inv = [1,1]
        self.inv = [0,1]
        
        """ 階乗を保存する配列を作成 """
        for i in range(2, N+1):
            self.fact.append((self.fact[-1]*i) % mod)
            self.inv.append((-self.inv[mod%i] * (mod//i))%mod)
            self.fact_inv.append((self.fact_inv[-1]*self.inv[i])%mod)
    
    """ 関数として使えるように、callで定義 """
    def __call__(self, n, r, mod=10**9+7):
        if (r<0) or (n<r):
            return 0
        return self.fact[n] * self.fact_inv[n-r] % mod

from collections import deque
n,k = map(int,input().split())
mod = 10**9 + 7
es = [[] for _ in range(n+1)]
d = [0]*(n+1)
for _ in range(n-1):
    a,b = map(int,input().split())
    es[a].append(b)
    es[b].append(a)
    d[a] += 1
    d[b] += 1

root = -1
for i in range(1, n+1):
    if d[i] == 1:
        root = i
        break

num_child = [0]*(n+1)
que = deque([])
for c in es[root]:
    que.append((root, c))

while que:
    p,c = que.pop()
    num_child[p] += 1
    for nx in es[c]:
        if nx!=p:
            que.append((c, nx))

c = Cmb(N=k)
ans = k

for e,child in enumerate(num_child[1:]):
    if e+1==root:
        cand = k-1
    else:
        cand = k-2
    if child==0:
        continue
    else:
        ans = ans*(c(cand, child)) % mod

print(ans%mod)

Solution (Python):
n,k = map(int,input().split())
ans = k
mod = 10**9+7
v = [[0] for i in range(n+1)]
for i in range(n-1):
    a,b = map(int,input().split())
    v[a].append(b)
    v[b].append(a)
if n == 1:
    print(k)
elif n == 2:
    print(k*(k-1))
else:
    q = [1]
    v[1][0] = 1
    
    while q:
        t = q.pop()
        
        cnt = 2-(t==1)
        for i in range(1,len(v[t])):
            
            if v[v[t][i]][0] == 0:
                q.append(v[t][i])
                v[v[t][i]][0] = 1
                ans = (ans*(k-cnt)) % mod
                cnt += 1
                
                
    
    print(ans)

Solution (Python):
import sys
from collections import deque

readline = sys.stdin.buffer.readline
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))

def solve():
    mod = 10**9 + 7
    n, k = nm()
    G = [list() for _ in range(n)]
    ans = 1
    for _ in range(n-1):
        u, v = nm()
        u -= 1; v -= 1
        G[u].append(v)
        G[v].append(u)
    q = deque()
    chi = [0]*n
    par = [-1]*n
    q.append(0)
    while q:
        v = q.popleft()
        c = k - chi[par[v]]
        if par[v] >= 0:
            chi[par[v]] += 1
            c -= 1
            if par[par[v]] >= 0:
                c -= 1
        ans = ans * c % mod
        for x in G[v]:
            if x != par[v]:
                par[x] = v
                q.append(x)
    print(ans)
    return

solve()

Solution (Python):
from collections import deque

int1 = lambda x: int(x) - 1
MOD = 10 ** 9 + 7

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

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


ans = K
for i in range(len(T[0])):
    ans = (ans * (K - i - 1)) % MOD
D = deque(T[0])
visited = {0}

while D:
    v = D.pop()
    visited.add(v)
    for i in range(len(T[v]) - 1):
        ans = (ans * (K - i - 2)) % MOD
    for x in T[v]:
        if x not in visited:
            D.append(x)
print(ans)

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

mod = 10 ** 9 + 7
def dfs(v, p, k):
    ret = 1
    if len(graph[v]) > k:
        return 0
    kc = k - 2
    if p == -1:
        kc = k - 1
    for vi in graph[v]:
        if vi != p:
            ret *= kc
            ret = ret % mod
            kc -= 1
    for vi in graph[v]:
        if vi != p:
            ret *= dfs(vi, v, k)
            ret = ret % mod
    return ret

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)
    
print((dfs(0, -1, k) * k) % mod)

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

mod = 10 ** 9 + 7
def dfs(v, p, k):
    ret = 1
    if len(graph[v]) > k:
        return 0
    kc = k - 2
    if p == -1:
        kc = k - 1
    for vi in graph[v]:
        if vi != p:
            ret *= kc
            ret = ret % mod
            kc -= 1
    for vi in graph[v]:
        if vi != p:
            ret *= dfs(vi, v, k)
            ret = ret % mod
    return ret

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)
    
print((dfs(0, -1, k) * k) % mod)

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


def main():
    input = stdin.buffer.readline
    n, k = map(int, input().split())
    g = [[] for _ in range(n)]
    for _ in range(n - 1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        g[a].append(b)
        g[b].append(a)

    mod = 10 ** 9 + 7

    q = deque([0])
    ans = k
    seen = [False] * n
    seen[0] = True

    while q:
        v = q.popleft()
        if v == 0:
            cand = k - 1
        else:
            cand = k - 2
        for n_v in g[v]:
            if not seen[n_v]:
                seen[n_v] = True
                ans = (ans * cand) % mod
                cand -= 1
                q.append(n_v)

    print(ans)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

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

mod = 10**9+7

def dfs(v,pr,k):
  if len(G[v]) > k:
    return 0
  
  kc = k-2
  if pr == -1:
    kc = k-1  
  
  ret = 1
  
  for vi in G[v]:
    if vi == pr:
      continue
    ret *= kc
    ret %= mod
    kc -= 1
    
  for vi in G[v]:
    if vi == pr:
      continue
    ret *= dfs(vi,v,k)
    ret %= mod
  
  return ret


n,k = map(int,input().split())
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)      
  
print(dfs(0,-1,k) * k % mod )

Solution (Python):
import sys
from collections import Counter
input = sys.stdin.readline
N, K = map(int, input().split())
if N == 1:
  print(K)
  exit(0)
elif N == 2:
  print(K * (K - 1))
  exit(0)
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)

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[K])
"""
for _ in range(Q):
  x = int(input())
  print(res[x])
"""