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 sys
input=sys.stdin.readline
from collections import deque
mod=1000000007
n,k=map(int,input().split())
Edges=[[] for _ in range(n)]
for _ in range(n-1):
    u,v=map(lambda x: int(x)-1,input().split())
    Edges[u].append(v)
    Edges[v].append(u)
Ans=[1]*n
Ans[0]=k
depth=[0]*n
Used=[False]*n
Used[0]=True
q=deque()
q.append(0)
while q:
    v=q.popleft()
    if v==0:
        cnt=k
    else:
        cnt=k-1
    for c in Edges[v]:
        if Used[c]:
            continue
        depth[c]=depth[v]+1
        d=depth[c]
        cnt-=1
        if cnt==0:
            print(0)
            exit()
        Ans[d]*=cnt
        Ans[d]%=mod
        q.append(c)
        Used[c]=True
max_depth=max(depth)
ans=1
for i in range(max_depth+1):
    ans*=Ans[i]
    ans%=mod
print(ans)

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

MOD = pow(10, 9) + 7
ans = 1
n, k = map(int, input().split())
visited = [False for _ in range(n)]
edges = {}

def dfs(i, c1, c2):
  global ans
  if visited[i]:
    return
  visited[i] = True
  ans = ans * (k-c1-c2) % MOD
  c0 = 0
  for e in edges[i]:
    if not visited[e]:
      dfs(e, 1, c1+c0)
      c0 += 1


def main():
  for _ in range(n-1):
    a, b = map(int, input().split())
    if a-1 not in edges:
      edges[a-1] = [b-1]
    else:
      edges[a-1].append(b-1)
    if b-1 not in edges:
      edges[b-1] = [a-1]
    else:
      edges[b-1].append(a-1)
  
  if n == 1:
    print(k)
  else:
    for i in range(n):
      if len(edges[i]) == 1:
        dfs(i, 0, 0)
    print(ans)


if __name__ == '__main__':
  main()

Solution (Python):

import sys
sys.setrecursionlimit(300000)

MOD = 1000000007  

def solve(N: int, K: int, a: "List[int]", b: "List[int]"):
    conn = [[] for _ in range(N)]
    for i in range(N - 1):
        conn[a[i] - 1].append(b[i] - 1)
        conn[b[i] - 1].append(a[i] - 1)

    def dfs(idx, cur, tmp, visited, ret):
        visited[idx] = True
        

        
        ret *= max(K - cur, 0)
        ret %= MOD

        cur = min(cur + 1, 2)
        for nex in conn[idx]:
            if not visited[nex]:
                ret = dfs(nex, cur, tmp, visited, ret)
                cur += 1
        return ret

    tmp = [0] * N
    visited = [False] * N
    ret = 1
    ret = dfs(0, 0, tmp, visited, ret)
    

    
    
    

    print(ret)
    return


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

if __name__ == '__main__':
    main()

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

E = [[] for i in range(n+1)]
for i in range(n-1):
    E[A[i][0]].append(A[i][1])
    E[A[i][1]].append(A[i][0])
    

B = [0 for i in range(n+1)]
H = [0 for i in range(n+1)]

def tuke(x,y,z):
    H[x] = 1
    B[x] = y
    y = max(k-z-1, k-2)
    for i in E[x]:
        if H[i] == 0:
            LI.append([i,y,z+1])
            y -= 1

LI = [[1,k,0]]

kk = 0
while kk < len(LI):
    tuke(LI[kk][0],LI[kk][1],LI[kk][2])
    kk += 1

ans = 1
for i in range(1,len(B)):
    ans = (ans * B[i]) % mod


print(ans)

Solution (Python):
MOD = 1000000007
N, K = map(int, input().split())
edge = {}
for _ in range(N - 1):
    a, b = map(int, input().split())
    if a not in edge:
        edge[a] = set()
    edge[a].add(b)
    if b not in edge:
        edge[b] = set()
    edge[b].add(a)


ans = K
q = [(1, None, 1)]
while len(q) > 0:
    par, parpar, depth = q.pop()
    if par not in edge:
        continue
    children = edge[par] - set([parpar])
    if len(children) == 0:
        continue
    if depth == 1:
        start = K - 1
    else:
        start = K - 2
    for i in range(len(children)):
        if start - i <= 0:
            ans = 0
            print(0)
            exit()
        else:
            ans *= start - i
        ans %= MOD
    for c in children:
        q.append((c, par, depth + 1))

print(ans)

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


from collections import deque
def main():
    N, K = map( int, input().split())
    E = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b = map( lambda x: x-1, map( int, input().split()))
        E[a].append(b)
        E[b].append(a)
    V = [0]*N
    V[0] = K
    d = deque()
    for i in range( len(E[0])):
        t = E[0][i]
        V[t] = K - 1 - i
        if K == i+1:
            print(0)
            return
        cnt = 0
        for v in E[t]:
            if V[v] == 0:
                d.append(v)
                if K == cnt+2:
                    print(0)
                    return
                V[v] = K-2-cnt
                cnt += 1
    while d:
        t = d.popleft()
        cnt = 0
        for v in E[t]:
            if V[v] == 0:
                d.append(v)
                if K == cnt+2:
                    print(0)
                    return
                V[v] = K-2-cnt
                cnt += 1
    ans = 1
    for v in V:
        ans *= v
        ans %= Q
    print(ans)
    
if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
MOD = 10**9 + 7
n, k = [int(item) for item in input().split()]
edge = [[] for _ in range(n)]

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

dq = deque()
dq.append([-1, 0, 0])

ans = 1
while(dq):
    prev, n, d = dq.popleft()
    if d == 0:
        ans *= k
        ans %= MOD
        same_dim = 0
        for item in edge[n]:
            if item == prev:
                continue
            ans *= k - 1 - same_dim
            ans %= MOD
            same_dim += 1
            dq.append([n, item, d+1])
    elif d == 1:
        same_dim = 0
        for item in edge[n]:
            if item == prev:
                continue
            ans *= k - 2 - same_dim
            ans %= MOD
            same_dim += 1
            dq.append([n, item, d+1])
    else:
        same_dim = 0
        for item in edge[n]:
            if item == prev:
                continue
            ans *= k - 2 - same_dim
            ans %= MOD
            same_dim += 1
            dq.append([n, item, d+1])
print(ans)

Solution (Python):
import sys
from collections import deque

fin = sys.stdin.readline

n, k = map(int, fin().split())
ab = [tuple(map(int, fin().split())) for i in range(n - 1)]
ab = [(a[0] - 1, a[1] - 1) for a in ab]

edge = {i: [] for i in range(n)}
for i in range(n - 1):
    edge[ab[i][0]].append(ab[i][1])
    edge[ab[i][1]].append(ab[i][0])

visited = [0] * n
queue = deque([0])
visited[0] = 1


def mul(a, b):
    return (a * b) % 1000000007


ans = k

pos = queue.popleft()
next_nodes = [e for e in edge[pos] if not visited[e]]
for i, ne in enumerate(next_nodes):
    queue.append(ne)
    visited[ne] = 1
    ans = mul(ans, k - i - 1)

while queue:
    pos = queue.popleft()
    next_nodes = [e for e in edge[pos] if not visited[e]]
    for i, ne in enumerate(next_nodes):
        queue.append(ne)
        visited[ne] = 1
        ans = mul(ans, k - 2 - i)

print(ans)

Solution (Python):
from collections import deque
N,K = list(map(int, input().split()))
MOD = int(1e9+7)

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


pc = [1] * N
pc[0] = 0
  
que = deque()
que.append(0)

ans = K
visited = set()
count = 0
while len(que)>0:
  x = que.pop()
  visited.add(x)
  parent = x
  for p in l[x]:
    if p in visited:
      continue
    
    pc[parent] += 1
    ans = ans * (K-pc[parent]) % MOD
    que.append(p)
    
print(ans)

Solution (Python):
def P(a,b,mod):
    r=1
    for i in range(b):
        r = (r*(a-i)) % mod
    return r

N, K = [int(c) for c in input().split()]
E = [[] for n in range(N)]
mod = 1000000007

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


n = K * P(K-1, len(E[0]), mod) % mod
for i in range(1, N):
    n = (n * P(K-2, len(E[i])-1, mod)) % mod

print(n)

Solution (Python):

import sys
from collections.abc import Iterable
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd

MOD = 1000000007  


class DGraph:
    def __init__(self, n, edges):
        self._vertice = [{} for _ in range(n)]
        for e in edges:
            self._vertice[e[0]][e[1]] = e[2] if len(e) == 3 else 1

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

    def edges(self, n=None):
        srcs = range(len(self)) if n is None else [n]
        return sum([[(s, d, c) for d, c in self._vertice[s].items()] for s in srcs], [])

    def transpose(self):
        tedges = [(t, f, c) for f, t, c in self.edges()]
        return DGraph(len(self), tedges)

    def cost(self, src, dst):
        return self._vertice[src].get(dst, float('inf'))

class Graph(DGraph):
    def __init__(self, n, edges):
        nd_edges = edges + [(d, s, c) for s, d, c in edges]
        super().__init__(n, nd_edges)

    def transpose(self):
        return self


def perm_mod(n, m, M):
    ret = 1
    for i in range(n, n - m, -1):
        ret = (ret * i) % M
    return ret


def solve(N: int, K: int, a: "List[int]", b: "List[int]"):
    es = [(ca-1, cb-1, 1) for ca, cb in zip(a, b)]
    g = Graph(N, es)

    ret = K
    visited = [False] * N
    q = deque([(0, K)])
    while 0 < len(q):
        cv, k = q.popleft()
        if visited[cv]:
            contains
        visited[cv] = True

        cs = [d for _, d, _ in g.edges(cv) if not visited[d]]
        ck = max(K - 2, k - 1)
        if 0 < len(cs):
            ret = (ret * perm_mod(ck, len(cs), MOD)) % MOD
        for c in cs:
            q.append((c, ck))
    return ret


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    K = int(next(tokens))  
    a = [int()] * (N-1)  
    b = [int()] * (N-1)  
    for i in range(N-1):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    result = solve(N, K, a, b)
    if isinstance(result, Iterable) and not isinstance(result, str):
        result = '\n'.join([str(v) for v in result])
    print(result)

if __name__ == '__main__':
    main()

Solution (Python):
import queue as qu

mod = 10 ** 9 + 7
N, K = map(int, input().split())
D = {n: set() for n in range(N)}
for n in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    D[a].add(b)
    D[b].add(a)

res = 1
F = [0] * N
already = [False] * N

q = qu.Queue()
q.put(0)
for _ in range(N):
    n = q.get()
    already[n] = True
    d = D[n]

    m = 2 if n else 1
    for b in d:
        if already[b]:
            continue
        F[b] = m
        m += 1
        q.put(b)
        
if max(F) >= K:
    print(0)
else:
    res = 1
    for f in F:
        res = (res * (K - f)) % mod
    print(res)

Solution (Python):
from collections import deque

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

color = [-1] * (N+1)
color[1] = K
queue = deque()
queue.append(1)
while queue:
    v = queue.popleft()
    cnt = 1 if v == 1 else 2
    for child_cand in adj[v]:
        if color[child_cand] == -1:
            queue.append(child_cand)
            color[child_cand] = K - cnt
            cnt += 1
ans = 1
for i in range(1, N+1):
    ans = (ans * color[i]) % mod
print(ans)

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

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


deg = [0]*N
deg2 = [0]*N
cnt = 1
visited = [False]*N
stack = [0]

while stack:
    u = stack.pop()
    visited[u] = True
    cnt *= K-deg[u]-deg2[u]
    cnt %= MOD
    for v in adj[u]:
        if not visited[v]:
            deg[v] += 1
            deg2[v] += deg[u]
            deg[u] += 1
            stack.append(v)

print(cnt)

Solution (Python):
import sys
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())
    adjL[A-1].append(B-1)
    adjL[B-1].append(A-1)

numCs = [-1]*N
def dfs1(vNow):
    numCs[vNow] = 0
    for v2 in adjL[vNow]:
        if numCs[v2] == -1:
            numCs[vNow] += 1
            dfs1(v2)

dfs1(0)

ps = [0]*N
p = 1
m = K
for _ in range(numCs[0]+1):
    p *= m
    p %= MOD
    m -= 1
ps[0] = p
for v in range(1, N):
    p = 1
    m = K-2
    for _ in range(numCs[v]):
        p *= m
        p %= MOD
        m -= 1
    ps[v] = p

ans = 1
for p in ps:
    ans *= p
    ans %= MOD

print(ans)

Solution (Python):

import sys
from collections import deque


MOD = 1000000007  

def solve(N: int, K: int, a: "List[int]", b: "List[int]"):
    adj = [[] for _ in range(N)]
    for aa, bb in zip(a, b):
        adj[aa-1].append(bb-1)
        adj[bb-1].append(aa-1)
    
    color = [K for _ in range(N)]
    visited = [False for _ in range(N)]
    Q = deque([])

    visited[0] = True
    Q.append((0, 0))

    while len(Q) > 0:
        u, x = Q.popleft()
        for v in adj[u]:
            if visited[v]:
                continue
            x += 1
            color[v] -= x
            Q.append((v, 1))
            visited[v] = True

    res = 1
    for c in color:
        res = (res * c) % MOD
    print(res)
    return



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

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque


class Mint:
    MOD = 1000000007  
    CACHE_FACTORIALS = [1, 1]

    def __init__(self, v):
        if self.__isally(v):
            self.v = v.v % self.MOD
        else:
            self.v = v % self.MOD

    @property
    def inv(self):
        return Mint(self.__minv(self.v))

    @classmethod
    def factorial(cls, v):
        for i in range(len(cls.CACHE_FACTORIALS), int(v) + 1):
            cls.CACHE_FACTORIALS.append(cls.CACHE_FACTORIALS[-1] * i % cls.MOD)
        return Mint(cls.CACHE_FACTORIALS[int(v)])

    @classmethod
    def perm(cls, n, r):
        if n < r or r < 0:
            return 0
        return cls.factorial(n) // cls.factorial(n - r)

    @classmethod
    def comb(cls, n, r):
        if n < r or r < 0:
            return 0
        return cls.perm(n, r) // cls.factorial(r)

    @classmethod
    def __isally(cls, v) -> bool:
        return isinstance(v, cls)

    @classmethod
    def __minv(cls, v) -> int:
        return pow(v, cls.MOD - 2, cls.MOD)

    @classmethod
    def __mpow(cls, v, w) -> int:
        return pow(v, w, cls.MOD)

    def __str__(self):
        return str(self.v)
    __repr__ = __str__

    def __int__(self):
        return self.v

    def __eq__(self, w):
        return self.v == w.v if self.__isally(w) else self.v == w

    def __add__(self, w):
        return Mint(self.v + w.v) if self.__isally(w) else Mint(self.v + w)
    __radd__ = __add__

    def __sub__(self, w):
        return Mint(self.v - w.v) if self.__isally(w) else Mint(self.v - w)

    def __rsub__(self, u):
        return Mint(u.v - self.v) if self.__isally(u) else Mint(u - self.v)

    def __mul__(self, w):
        return Mint(self.v * w.v) if self.__isally(w) else Mint(self.v * w)
    __rmul__ = __mul__

    def __floordiv__(self, w):
        return Mint(self.v * self.__minv(w.v)) if self.__isally(w) else Mint(self.v * self.__minv(w))

    def __rfloordiv__(self, u):
        return Mint(u.v * self.__minv(self.v)) if self.__isally(u) else Mint(u * self.__minv(self.v))

    def __pow__(self, w):
        return Mint(self.__mpow(self.v, w.v)) if self.__isally(w) else Mint(self.__mpow(self.v, w))

    def __rpow__(self, u):
        return Mint(self.__mpow(u.v, self.v)) if self.__isally(u) else Mint(self.__mpow(u, self.v))


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

ans = Mint(1)
q = deque()
q.append((1, 0, 0))
while len(q):
    n, i, prev = q.pop()
    if K - i <= 0:
        print(0)
        exit()
    ans *= K - i
    j = 1 if i == 0 else 2
    for m in tree[n]:
        if prev == m:
            continue
        q.append((m, j, n))
        j += 1
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(200000)
n,k = map(int,input().split())
mod = 10**9+7
gr = [set() for _ in range(n+1)]
for i in range(n-1):
    a,b = map(int,input().split())
    gr[a].add(b)
    gr[b].add(a)
ans = [0]*(n+1)
done = [0]*(n+1)
done[1] = -1
done[0] = -2
def dfs2(gr,p,v,done,ans):
    ans[v] = k-2-done[p]
    for x in gr[v]:
        if x == p:
            continue
        dfs2(gr,v,x,done,ans)
        done[v] += 1
    return
dfs2(gr,0,1,done,ans)
m = 1
for x in ans[1:]:
    m = m*x%mod
print(m)

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

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].append(b)
    E[b].append(a)

Closed = [False] * (N+1)
Close_cnt = [1] * (N+1)
ans = 1
mod = 10**9 + 7
def dfs(n, start=False):
    global ans
    Closed[n] = True
    if start:
        Close_cnt[n] = 0
    col = K
    for v in E[n]:
        if Closed[v]:
            col -= Close_cnt[v]
    ans = ans * col % mod
    Close_cnt[n] += 1

    for v in E[n]:
        if not Closed[v]:
            dfs(v)
            Close_cnt[n] += 1
dfs(1, True)
print(ans)

Solution (Python):
MOD = 1000000007

N, K = map(int, input().split())
uv = {}
for i in range(N-1):
    a, b = map(int, input().split())
    if a in uv:
        uv[a].append(b)
    else:
        uv[a] = [b]

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

f = 1
for u in uv:
    if len(uv[u]) == 1:
        f = u
        break


ans = 1
b = [False] * (N+1)
ulist = [[f, 0]]
while ulist:
    u, pNum = ulist[-1]
    ulist.pop()
    b[u] = True

    uPtn = K - pNum
    ans = ans*uPtn % MOD

    
    cnt = 1
    if pNum == 0:
        cnt = 0
    if u in uv:
        for v in uv[u]:
            if b[v]:
                continue
            ulist.append([v, 1 + cnt])
            cnt += 1

print(ans)

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))

from collections import deque
from sys import exit

MOD = 1000000007

n, k = getList()
if n == 1:
    print(k % MOD)
    exit()
vertex = [[] for i in range(n)]

for i in range(n-1):
    a, b = getList()
    vertex[a-1].append(b-1)
    vertex[b-1].append(a-1)

for i, v in enumerate(vertex):
    if len(v) == 1:
        root = i
        break

MOD = 1000000007


q = deque([])
q.append(vertex[root][0])
q.append(-1)
visited = [0 for i in range(n)]
visited[root] = 1
ans = k
uni = 1
while(q):
    
    nxt = q.popleft()

    if nxt == -1:
        uni = 2
        continue
    if visited[nxt] == 1:
        continue
    for edge in vertex[nxt]:
        if visited[edge] == 0:
            q.append(edge)
    q.append(-1)
    ans *= k - uni
    ans = ans % MOD
    uni += 1
    visited[nxt] = 1
    

print(ans)

Solution (Python):


import queue

n, k = list(map(int, input().split()))
edges = [list(map(int, input().split())) for _ in range(n-1)]

def add_edge(u, v ):
	G[u].append(v)
	G[v].append(u)

G = [[] for _ in range(n)] 
for edge in edges:
	add_edge(edge[0]-1, edge[1]-1)

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

n_colors = [-1] * n
n_colors[0] = k

count = 0
for v in G[0]:
	q.put(v)
	n_colors[v] = k - count - 1 
	count += 1

while(q.qsize() > 0):
	now = q.get()
	count = 0
	for v in G[now]:
		if n_colors[v] >= 0:
			pass
		else:
			q.put(v)
			n_colors[v] = k - count - 2
			count += 1

			if n_colors[v] == 0:
				print(0)
				exit()

ans = 1
for i in range(n):
	ans *= n_colors[i]
	ans %= (10 ** 9 + 7)

print(ans)

Solution (Python):
from collections import deque

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

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

dp = [0] * N
visited = [False] * N
queue = deque([0])

ret = 1
while queue :
    cur = queue.popleft()
    visited[cur] = True
    nvisited = 0
    
    for nex in v[cur] :
        if visited[nex] :
            nvisited += dp[nex] + 1
            dp[cur] += 1
            dp[nex] += 1
        else :
            queue.append(nex)
               
    if nvisited >= K :
        ret = 0
        break
    else :
        ret *= (K-nvisited)
        ret %= MOD

print(ret)

Solution (Python):
import sys
input = sys.stdin.readline
from collections import deque
mod=10**9+7
N,K=map(int,input().split())
tree=[[] for i in range(N)]
for i in range(N-1):
    a,b=map(int,input().split())
    a,b=a-1,b-1
    tree[b].append(a)
    tree[a].append(b)

H=deque()
visit=[-mod]*N
visit[0]=K
inchild=[0]*N
H.append(0)
while H:
    y=H.popleft()
    t=K-2
    if y==0:
        t=K-1
    for x in tree[y]:
        if visit[x]!=-mod:
            continue
        visit[x]=t
        H.append(x)
        t-=1

ans=1
for k in visit:
    if k<=0:
        print(0)
        sys.exit()
    ans*=k
    ans%=mod
print(ans)

Solution (Python):
from collections import defaultdict

def main():
    num, color_num = map(int, input().split())
    data = [list(map(int, input().split())) for i in range(num - 1)]
    graph_data = defaultdict(set)
    mod = 10 ** 9 + 7

    for i in range(num - 1):
        a, b = data[i]
        graph_data[a].add(b)
        graph_data[b].add(a)

    ans_data = [0 for i in range(num + 1)]
    ans_data[1] = color_num % mod

    now_set = set()
    next_set = set()
    now_set.add(1)

    while len(now_set) > 0:
        for now_ele in now_set:
            if now_ele == 1:
                count = color_num - 1
            else:
                count = color_num - 2

            for next_ele in graph_data[now_ele]:
                if ans_data[next_ele] != 0:
                    continue
                if count <= 0:
                    ans_data[next_ele] = -1
                else:
                    ans_data[next_ele] = count % mod
                count -= 1
                next_set.add(next_ele)
        now_set = next_set
        next_set = set()

    ans = 1
    for i in range(1, num + 1):
        if ans_data[i] <= 0:
            ans = 0
            break
        ans *= ans_data[i]
        ans %= mod

    print(ans)












if __name__ == '__main__':
    main()

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

mod=10**9+7
n,k=map(int,input().split())
N=[[] for i in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  N[a-1]+=[b-1]
  N[b-1]+=[a-1]
Chk=[0]*n
S=[0]
Chk[0]=1
ans=k
while S:
  ss=S.pop()
  for sss in N[ss]:
    if Chk[sss]>0:
      continue
    else:
      ans=(ans*max(k-Chk[ss],0))%mod
      Chk[ss]+=1
      Chk[sss]=2
      S.append(sss)
print(ans%mod)

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

e_list = [[] for i in range(N)]

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

if K==1:
    if N==1:
        print(1)
    else:
        print(0)
else:
    mod=10**9+7
    combA = [1]
    ca = 1
    for i in range(K-1):
        ca = (ca*(K-1-i))%mod
        combA.append(ca)
    combB = [1]
    cb = 1
    for i in range(K-2):
        cb = (cb*(K-2-i))%mod
        combB.append(cb)
    flag=True
    
    
    ans = K
    mod=10**9+7
    vi = 0 
    from collections import deque
    Q = deque([vi])
    checked_list = [False for i in range(N)]
    checked_list[vi]=True
    while len(Q)>0:
        v = Q.pop()
        count=0
        for v1 in e_list[v]:
            if not checked_list[v1]:
                checked_list[v1]=True
                Q.appendleft(v1)
                count+=1
        
        if v==0:
            if count<=K-1:
                ans= (ans*combA[count])%mod
            else:
                flag=False
                break
        else:
            if count<=K-2:
                ans= (ans*combB[count])%mod
                
            else:
                flag=False
                break
    if flag:
        print(ans)
    else:
        print(0)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 5 + 5)


def dfs(v, p, f):
    ret = f
    child_free = k - 1 if f == k else k - 2
    for u in links[v]:
        if u == p:
            continue
        pat = dfs(u, v, child_free)
        if pat == 0:
            ret = 0
            break
        ret = ret * pat % MOD
        child_free -= 1
    
    return ret


n, k = list(map(int, input().split()))
MOD = 10 ** 9 + 7
RK = pow(k, MOD - 2, MOD)
links = [set() for _ in range(n)]
for line in sys.stdin:
    a, b = map(int, line.split())
    a -= 1
    b -= 1
    links[a].add(b)
    links[b].add(a)
ans = dfs(0, -1, k)
print(ans)

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

def comb(n,k,p):
  """power_funcを用いて(nCk) mod p を求める"""
  from math import factorial
  if n<0 or k<0 or n<k: return 0
  if n==0 or k==0: return 1
  a=factorial(n) %p
  b=factorial(k) %p
  c=factorial(n-k) %p
  return (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p
def power_func(a,b,p):
  """a^b mod p を求める"""
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p ))%p

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

ans = K
visit = [False]*(N+1)
visit[1] = True
queue = tree[1][:]
for i in range(len(queue)):
    ans *= K-1-i
    ans %= 1000000007
    visit[queue[i]] = True


while len(queue) > 0:
    nextqueue = []
    for now in queue:
        nexttemp = []
        for next in tree[now]:
            if not visit[next]:
                nexttemp.append(next)
                visit[next] = True
        nextqueue.extend(nexttemp)
        for i in range(len(nexttemp)):
            ans *= K-2-i
            ans %= 1000000007
    queue = nextqueue[:]

print(ans)

Solution (Python):
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())


class Combination:
    def __init__(self,N):
        self.fac = [1]*(N+1)
        for i in range(1,N+1):
            self.fac[i] = (self.fac[i-1]*i)%mod
        self.invmod = [1]*(N+1)
        self.invmod[N] = pow(self.fac[N],mod-2,mod)
        for i in range(N,0,-1):
            self.invmod[i-1] = (self.invmod[i]*i)%mod

    def C(self,n,k):
        if n < k:
            return 0
        return self.fac[n]*self.invmod[k]%mod *self.invmod[n-k] %mod

    def P(self,n,k):
        if n < k or k < 0:
            return 0
        return self.fac[n]*self.invmod[k]%mod


N,K = inpl()
lines = defaultdict(set)
for _ in range(N-1):
    x,y = inpl()
    x,y = x-1,y-1
    lines[x].add(y)
    lines[y].add(x)

lines2 = defaultdict(set)
visited = [False]*N
def dfs(s):
    visited[s] = True
    for t in lines[s]:
        if not visited[t]:
            lines2[s].add(t)
            dfs(t)
dfs(0)

def solve(s,first):
    L = len(lines2[s])
    if L == 0:
        return 1
    if first:
        ans = Comb.P(K-1,K-1-L)
    else:
        ans = Comb.P(K-2,K-2-L)
    for t in lines2[s]:
        ans *= solve(t,False)
        ans %= mod
    return ans

Comb = Combination(max(K,N)+3)

print(solve(0,True)*K%mod)

Solution (Python):
N,K=list(map(int,input().strip().split(' ')))
graph=[[] for i in range(N)]
for _ in range(N-1):
    a,b=list(map(int,input().strip().split(' ')))
    a-=1
    b-=1
    graph[a]+=[b]
    graph[b]+=[a]

from collections import deque
q=deque([0])
parent=[-1]*N
Ans=K
MOD=10**9+7
while q:
    node=q.popleft()
    deduct=0
    if node==0:
        deduct=0
    else:
        deduct=1
    for adj in graph[node]:
        if adj!=parent[node]:
            deduct+=1
            
            Ans*=max(K-deduct,0)
            Ans%=MOD
            parent[adj]=node
            q+=[adj]
print(Ans)

Solution (Python):
class perm():
  F = [1, 1]
  Fi = [1, 1]
  I = [0, 1]
  def __init__(self, num, mod):
    self.MOD = mod
    for i in range(2, num + 1):
      self.F.append((self.F[-1] * i) % mod)
      self.I.append(mod - self.I[mod % i] * (mod // i) % mod)
      self.Fi.append(self.Fi[-1] * self.I[i] % mod)
  def per(self, n, k):
    if n < k: return 0
    if n < 0 or k < 0: return 0
    return self.F[n] * (self.Fi[n - k] % self.MOD) % self.MOD

class Tree:
  C, RL = {}, {}
  R, T, N, D = None, None, None, None
  def __init__(s, num):
    s.N = num
  def setC(s, a, b):
    if a in s.C: s.C[a].append(b)
    else: s.C[a] = [b]
    if b in s.C: s.C[b].append(a)
    else: s.C[b] = [a]
  def makeRank(s, root):
    s.R = [0] * s.N
    s.R[root] = 1
    s.RL[1] = [root]
    F = [root]
    s.D = 2
    while F != []:
      Ft = []
      s.RL[s.D] = []
      for i in F:
        for j in s.C[i]:
          if s.R[j] == 0:
            s.R[j] = s.D
            Ft.append(j)
            s.RL[s.D].append(j)
      s.D += 1
      F = Ft
  def dfs(s, x):
    S = [x]
    ans = K
    while S != []:
      k = S.pop()
      n = 0
      for i in s.C[k]:
        if s.R[i] > s.R[k]:
          n += 1
          S.append(i)
      if n != 0:
        if k == x:
          if n > K - 1:
            return 0
          ans = ans * P.per(K - 1, n) % MOD
        else:
          if n > K - 2:
            return 0
          ans = ans * P.per(K - 2, n) % MOD
    return ans

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

if N == 1:
  print(K)
  exit()
  
P = perm(K, MOD)

T = Tree(N)
for a, b in ab:
  T.setC(a - 1, b - 1)

T.makeRank(0)

print(T.dfs(0))