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

def solve(g, p, index, y, z, k):
    p[index] = k - y - z
    x = 1
    for i in g[index]:
        if p[i] == -1:
            solve(g, p, i, x, y, k)
            y += 1

def main():
    n, k = map(int, input().split())
    graph =[[] for _ in range(n)]
    p = [-1]*n
    for _ in range(n-1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        graph[a].append(b)
        graph[b].append(a)
    s = None
    for i in range(n):
        if len(graph[i]) == 1:
            s = i
            break
    if s is None:
        print(k)
        sys.exit()
    solve(graph, p, s, 0, 0, k)
    ans = 1
    for i in p:
        ans *= i
        ans %= 10**9 + 7
    print(ans)

if __name__ == "__main__":
    main()

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

MOD = 10**9+7

class Comb:
    def __init__(self, N):
        self.fac = [1] * (N+1)
        for i in range(2, N+1): self.fac[i] = self.fac[i-1] * i % MOD

    def pow(self, a, b):
        res = 1
        while b:
            if b & 1: res = res * a % MOD
            a = a**2 % MOD
            b >>= 1
        return res

    def comb(self, n, r):
        if r < 0 or r > n: return 0
        return (self.fac[n] * self.pow(self.fac[r], MOD-2)) % MOD * self.pow(self.fac[n-r], MOD-2) % MOD

    def permutation(self, n, r):
        if r == 0: return 1
        return self.fac[n] * self.pow(self.fac[n-r], MOD-2) % MOD

def main():
    N, K = list(map(int, input().split()))
    g = [0] * (N+1)
    
    for i in range(N-1):
        a, b = list(map(int, input().split()))
        g[a] += 1
        g[b] += 1
    
    comb = Comb(K)

    ans = K * comb.permutation(K-1, g[1]) % MOD
    K -= 2
    for i in range(2, N+1):
        if K < g[i]-1: ans = 0; break

        ans = ans * comb.permutation(K, g[i]-1) % MOD

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

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

MOD = 10**9+7

class Comb:
    def __init__(self, N):
        self.fac = [1] * (N+1)
        for i in range(2, N+1): self.fac[i] = self.fac[i-1] * i % MOD

    def pow(self, a, b):
        res = 1
        while b:
            if b & 1: res = res * a % MOD
            a = a**2 % MOD
            b >>= 1
        return res

    def comb(self, n, r):
        if r < 0 or r > n: return 0
        return (self.fac[n] * self.pow(self.fac[r], MOD-2)) % MOD * self.pow(self.fac[n-r], MOD-2) % MOD

    def permutation(self, n, r):
        return self.fac[n] * self.pow(self.fac[n-r], MOD-2) % MOD
      
def main():
    N, K = list(map(int, input().split()))
    g = [0] * (N+1)
    
    for i in range(N-1):
        a, b = list(map(int, input().split()))
        g[a] += 1
        g[b] += 1
    
    comb = Comb(K)

    ans = K * comb.permutation(K-1, g[1]) % MOD
    K -= 2
    for i in range(2, N+1):
        if K < g[i]-1: ans = 0; break

        ans = ans * comb.permutation(K, g[i]-1) % MOD

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

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

MOD = 10**9+7

class Comb:
    def __init__(self, N):
        self.fac = [1] * (N+1)
        for i in range(2, N+1): self.fac[i] = self.fac[i-1] * i % MOD

    def pow(self, a, b):
        res = 1
        while b:
            if b & 1: res = res * a % MOD
            a = a**2 % MOD
            b >>= 1
        return res

    def comb(self, n, r):
        if r < 0 or r > n: return 0
        return (self.fac[n] * self.pow(self.fac[r], MOD-2)) % MOD * self.pow(self.fac[n-r], MOD-2) % MOD

    def permutation(self, n, r):
        return self.fac[n] * self.pow(self.fac[n-r], MOD-2) % MOD

def main():
    N, K = list(map(int, input().split()))
    g = [[] for i in range(N+1)]
    ans = K

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

    comb = Comb(K)

    q = deque([(-1, 1)])
    while q:
        par, chi = q.pop()
        r = len(g[chi])-1
        if par == -1: k = K-1; r += 1
        else: k = K-2
        if k < r: ans = 0; break

        ans = ans * comb.permutation(k, r) % MOD
        for c in g[chi]:
            if c != par: q.append((chi, c))

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

Solution (Python):
N, K = (int(i) for i in input().split())

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

from collections import deque
def BFS(N, K, graph, start):
    c = [-1 for i in range(N)]
    Q = deque([])
    Q.append(start)
    c[start] = K
    while Q:
        v = Q.popleft()
        if v == start:
            lc = K - 1
        else:
            lc = K - 2
        for u in graph[v]:
            if c[u] == -1:
                if lc == 0:
                    print(0)
                    exit()
                c[u] = lc
                lc -= 1
                Q.append(u)
    return c

c = BFS(N, K, graph, 0)

MOD = 10**9+7
ans = 1
for i in c:
    ans *= i
    ans %= MOD
print(ans)

Solution (Python):
from collections import deque
n,k = map(int,input().split())
l = [[] for i in range(n+1)]
for i in range(n-1):
    a,b = map(int,input().split())
    l[a].append(b)
    l[b].append(a)
rl = [0 for i in range(n+1)]
nl = [0 for i in range(n+1)]
ans = 0
nl[0] = -1
d = deque()
d.append([1,0])
rl2 = [0 for i in range(n+1)]
rl2[0] = 1
while len(d):
    [now,p] = d.popleft()
    
    rl[now] = k - nl[p] - 1
    nl[p] += 1
    rl2[now] = 1
    if now != 1:
        nl[now] += 1
    for i in l[now]:
        if rl2[i] == 0:
            d.append([i,now])
ans = 1
mod = 10**9+7

for i in range(1,n+1):
    ans *= rl[i]
    ans %= mod
if ans > 0:
    print(ans)
else:
    print(0)

Solution (Python):
from collections import deque

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

MOD = 1000000007

g = [[] * 1 for i 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)

d = [-1 for i in range(n)]

q = deque([])
num = k-1
d[0] = k
for to in g[0]:
    if d[to] == -1:
        d[to] = num
        num -= 1
        if num < 0:
            num = 0
        q.append(to)

while q:
    v = q.popleft()
    num = k-2
    for to in g[v]:
        if d[to] == -1:
            d[to] = num
            num -= 1
            if num < 0:
                num = 0
            q.append(to)

ans = 1
for i in d:
    ans *= i
    ans %= MOD

print(ans)

Solution (Python):
n,k=map(int,input().split())
mod=10**9+7
tree=[[] for i in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  tree[a-1].append(b-1)
  tree[b-1].append(a-1)
stack=[0]
visited=[True]+[False]*n
ans=k
while stack:
  v=stack.pop()
  c=k-2 if v!=0 else k-1
  for i in tree[v]:
    if not visited[i]:
      ans=(ans*c)%mod
      c-=1
      stack.append(i)
      visited[i]=True
print(ans)

Solution (Python):
import collections
from collections import deque
def tree(s,m):
    INF=-10**9
    visited = [INF for i in range(n)]

    def bfs():
        d = deque()
        d.append(s)
        ans=m
        mod=10**9+7
        count=0
        visited[s]=0
        while len(d):
            v = m
            x = d.popleft()
            if count<2:
                count+=1
            v-=count
            for i in range(len(b[x])):
                y=b[x][i]
                if visited[y] == INF:
                    visited[y]=0
                    d.append(y)
                    ans*=v
                    ans%=mod
                    v-=1
        return ans
    return bfs()



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

for i in range(n-1):
    b[a[i][0]-1].append(a[i][1]-1)
    b[a[i][1]-1].append(a[i][0]-1)

c=tree(0,m)
print(c)

Solution (Python):
import collections
from collections import deque
def tree(s,m):
    INF=-10**9
    visited = [INF for i in range(n)]

    def bfs():
        d = deque()
        d.append(s)
        ans=m
        mod=10**9+7
        count=0
        visited[s]=0
        while len(d):
            v = m
            x = d.popleft()
            if count<2:
                count+=1
            v-=count
            for i in range(len(b[x])):
                y=b[x][i]
                if visited[y] == INF:
                    visited[y]=0
                    d.append(y)
                    ans*=v
                    ans%=mod
                    v-=1
        return ans
    return bfs()


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

n,m= map(int, input().split())
a = [list(map(int, input().split())) for i in range(n-1)]
b = [[] for i in range(n)]
uf=UnionFind(n)
for i in range(n-1):
    b[a[i][0]-1].append(a[i][1]-1)
    b[a[i][1]-1].append(a[i][0]-1)
    uf.union(a[i][0]-1,a[i][1]-1)

u=uf.find(0)


c=tree(u,m)
print(c)

Solution (Python):
from collections import defaultdict, deque
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    return g1[n] * g2[r] % mod

mod = 10**9+7 
N = 10**6
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())
dic = defaultdict(list)
for i in range(N-1):
  a, b = map(int, input().split())
  dic[a-1] += [b-1]
  dic[b-1] += [a-1]

log = [float('inf')]*N
log[0] = 0
q = deque([0])
ans = K
while q:
  p = q.popleft()
  if log[p]<1:
    ans *= cmb(K-1,K-1-len(dic[p]),mod)
  else:
    ans *= cmb(K-2,K-1-len(dic[p]),mod)
  ans %= mod
  for e in dic[p]:
    if log[e]>log[p]+1:
      q += [e]
      log[e] = log[p]+1
print(ans)

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

U = 10**5
MOD = 10**9+7
 
fact = [1]*(U+1)
fact_inv = [1]*(U+1)
 
for i in range(1,U+1):
    fact[i] = (fact[i-1]*i)%MOD
fact_inv[U] = pow(fact[U], MOD-2, MOD)
 
for i in range(U,0,-1):
    fact_inv[i-1] = (fact_inv[i]*i)%MOD
 
def perm(n, k):
    if k < 0 or k > n:
        return 0
    z = fact[n]
    z *= fact_inv[n-k]
    z %= MOD
    return z

n, k = map(int, input().split())
T = [[] for _ in range(n)]
for _ in range(n-1):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  T[a].append(b)
  T[b].append(a)
  
seen = [False]*n
def dfs(v):
  seen[v] = True
  res = 1
  b = 1
  count = 0
  for i in T[v]:
    if seen[i]:
      b = 2
      continue
    count += 1
    res *= dfs(i)
    res %= MOD
  res *= perm(k-b, count)
  return res

ans = dfs(0) * k % MOD
print(ans)

Solution (Python):
n,k=map(int,input().split())
path=[[] 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)
mod=10**9+7
stack=[0]
visited=[1]+[0]*(n-1)
ans=k
while stack:
  v=stack.pop(0)
  c=k-2 if v!=0 else k-1
  for d in path[v]:
    if visited[d]:
      continue
    visited[d]=1
    ans=(ans*c)%mod
    c-=1
    stack.append(d)
print(ans)

Solution (Python):

n,k = map(int,input().split())
mod = 10 ** 9 + 7
peer = [[] for _ in range(n)]
for _ in range(n-1):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  peer[a].append(b)
  peer[b].append(a)
now = [0]
pst = [[] for _ in range(n)]
seen = [0 for _ in range(n)]
seen[0] = 1
while now:
  last = now
  now = []
  for x in last:
    for y in peer[x]:
      if seen[y] == 0:
        seen[y] = 1
        now.append(y)
        pst[x].append(y)

for i in range(n):
  if i == 0:
    ans = k
    for j in range(len(pst[0])):
      ans *= k-1-j
      ans %= mod
    continue
  for j in range(len(pst[i])):
    ans *= k-2-j
    ans %= mod
print(ans)

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

mod=10**9+7
MAX=10**5+100

g1=[1,1]
g2=[1,1]
for i in range(2,MAX+1):
    num_1=g1[-1]*i%mod
    g1.append(num_1)
    g2.append(pow(num_1,mod-2,mod))

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

data=[[] for i in range(N+1)]
for A,B in AB:
    data[A].append(B)
    data[B].append(A)
    
count=[0]*(N+1)
flag=[0]*(N+1)
que=[1]
flag[1]=1
while que:
    h=[]
    for u in que:
        cnt=0
        for v in data[u]:
            if flag[v]==0:
                flag[v]=1
                cnt+=1
                h.append(v)
        count[u]=cnt
    que=h

if K-1-count[1]<0:
    print(0)
    sys.exit()
ans=K*g1[K-1]*g2[K-1-count[1]]%mod

for i in range(2,N+1):
    if count[i]==0:
        continue
    else:
        if K-2-count[i]<0:
            print(0)
            sys.exit()
        ans=ans*g1[K-2]*g2[K-2-count[i]]%mod
    
print(ans)

Solution (Python):
import sys

MOD = 10**9 + 7

n, k, *ab = map(int, sys.stdin.read().split())
ab = zip(*[iter(ab)] * 2)
g = [[] for _ in range(n+1)]
for a, b in ab:
    g[a].append(b)
    g[b].append(a)

def main():
    stack = [1]
    coloring = [None] * (n + 1); coloring[1] = k
    par = [None] * (n + 1)
    while stack:
        u = stack.pop()
        r = k - 1
        if par[u]:
            r -= 1
        for v in g[u]:
            if v != par[u]:
                par[v] = u
                if r < 0:
                    return 0
                coloring[v] = r
                r -= 1
                stack.append(v)
    
    res = 1
    for i in range(1, n+1):
        res *= coloring[i]
        res %= MOD
    
    return res

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

Solution (Python):
import sys

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

def permutation(n, x, mod=10**9+7):
    
    tmp = 1
    for i in range(n, n-x, -1):
        tmp = (tmp * i) % mod
    return tmp

N, K = lr()
edges = [[] for _ in range(N+1)]
MOD = 10 ** 9 + 7

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

parent = [0] * (N+1)
stack = [1] 
while stack:
    node = stack.pop()
    for x in edges[node]:
        if x == parent[node]:
            continue
        parent[x] = node
        stack.append(x)

answer = K
stack = [1]
while stack:
    node = stack.pop()
    if parent[node] == 0:
        answer *= permutation(K-1, len(edges[node]))
    else:
        answer *= permutation(K-2, len(edges[node])-1)
    for next in edges[node]:
        if next == parent[node]:
            continue
        elif len(edges[next]) >= 2:
            stack.append(next)
    answer %= MOD

print(answer)

Solution (Python):
from collections import defaultdict
v = defaultdict(list)
mod = 10**9+7

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

visited = [False]*(N+1)
ans = 1

q = [(1, 0, 0)]
while q:
    pos, parent, score = q.pop()
    visited[pos] = True
    ans *= (K-score)
    ans %= mod 
   
    a = 1 if pos==1 else 2
    b = 0

    for i in v[pos]:
        if visited[i]:continue
        q.append((i, pos, a+b))
        b += 1

print(ans)

Solution (Python):
import collections
N,K=map(int,input().split())
G=[set() for i in range(N)]
for i in range(N-1):
  a,b=map(int,input().split())
  a-=1
  b-=1
  G[a].add(b)
  G[b].add(a)
m=0
id=9
for i in range(N):
  if len(G[i])>m:
    id=i
    m = len(G[i])
q=collections.deque()
q.append(0)
colored=[False]*N
colored[0]=True
from math import factorial
mod = 10**9 + 7
ans = K
while(q):
  x= q.popleft()
  count=0
  for y in G[x]:
    if colored[y]:
      continue
    else:
      q.append(y)
      colored[y]=True
      count+=1
      
  for i in range(count):
    ans *= K-1-(len(G[x])-count)-i
    ans %= mod
  
print(ans)

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


MOD = 10 ** 9 + 7


def prepare(n):
    global MOD
    modFacts = [0] * (n + 1)
    modFacts[0] = 1
    for i in range(n):
        modFacts[i + 1] = (modFacts[i] * (i + 1)) % MOD

    invs = [1] * (n + 1)
    invs[n] = pow(modFacts[n], MOD - 2, MOD)
    for i in range(n, 1, -1):
        invs[i - 1] = (invs[i] * i) % MOD

    return modFacts, invs


def dfs(n):
    global MOD
    var = 1
    isLeaf = True
    for e in edge[n]:
        if status[e] == 0:
            isLeaf &= False
            status[e] = 1
            var *= dfs(e)
            var %= MOD
    if isLeaf:
        ans = 1
    else:
        ans = nPk(K - 2 + (n == 0), len(edge[n]) - 1 + (n == 0))
        ans *= var
        ans %= MOD
    Leaf[n] = ans
    return ans


def nPk(n, k):
    global MOD
    x1 = modFacts[n]
    x2 = invs[n - k]
    ans = x1 * x2
    return ans % MOD


N, K = map(int, input().split())
edge = [[] for _ in range(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)


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

modFacts, invs = prepare(K)


Leaf = [0] * N
status = [0] * N
status[0] = 1
result = dfs(0)

print((result * K) % MOD)

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


MOD = 10 ** 9 + 7


def prepare(n):
    global MOD
    modFacts = [0] * (n + 1)
    modFacts[0] = 1
    for i in range(n):
        modFacts[i + 1] = (modFacts[i] * (i + 1)) % MOD

    invs = [1] * (n + 1)
    invs[n] = pow(modFacts[n], MOD - 2, MOD)
    for i in range(n, 1, -1):
        invs[i - 1] = (invs[i] * i) % MOD

    return modFacts, invs


def dfs(n, free):
    cnt = free
    rst = True
    for e in edge[n]:
        if status[e] == -1:
            cnt += 1
            status[e] = cnt
            rst &= dfs(e, 1)
    if cnt > K - 1:
        rst &= False
    return rst


N, K = map(int, input().split())
edge = [[] for _ in range(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)

modFacts, invs = prepare(K)


status = [-1] * N
status[0] = 0
result = dfs(0, 0)
if result:
    ans = 1
    for s in status:
        ans *= (K - s)
        ans %= MOD
else:
    ans = 0

print(ans)

Solution (Python):

import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1
sys.setrecursionlimit(10**7)

n,k=map(int,input().split())
G=[[] for i 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)

class InverseTable:
    __slots__ = ['In', 'fac', 'Ifac']

    def __init__(self, mod, maxnum):
        self.In = [0, 1]; self.fac = [1, 1]; self.Ifac = [1, 1]
        for i in range( 2, maxnum + 1 ):
            self.In.append( ( -self.In[mod % i] * (mod//i) ) % mod )
            self.fac.append( ( self.fac[-1] * i ) % mod )
            self.Ifac.append( (self.Ifac[-1] * self.In[-1]) % mod )
        
    def cmb(self, n, r):
        if ( r<0 or r>n ): return 0
        r = min(r, n-r)
        return self.fac[n] * self.Ifac[r] * self.Ifac[n-r] % mod
    
    def per(self, n, r):
        if ( r<0 or r>n ): return 0
        return self.fac[n] * self.Ifac[n-r] % mod

invt = InverseTable(mod, 2*10**5)



def dfs(s,node,parent):
    if len(G[node])>=k: return 0
    elif len(G[node])-s==0: return 1
    
    else: result=invt.per(k-1-s,len(G[node])-s)
    for i ,di in enumerate(G[node]):
        if di == parent: continue
        result*=dfs(1,di,node); result%=mod
    
    return result

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

Solution (Python):

import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1
sys.setrecursionlimit(10**7)

n,k=map(int,input().split())
G=[[] for i 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)

class InverseTable:
    __slots__ = ['In', 'fac', 'Ifac']

    def __init__(self, mod, maxnum):
        self.In = [0, 1]; self.fac = [1, 1]; self.Ifac = [1, 1]
        for i in range( 2, maxnum + 1 ):
            self.In.append( ( -self.In[mod % i] * (mod//i) ) % mod )
            self.fac.append( ( self.fac[-1] * i ) % mod )
            self.Ifac.append( (self.Ifac[-1] * self.In[-1]) % mod )
        
    def cmb(self, n, r):
        if ( r<0 or r>n ): return 0
        r = min(r, n-r)
        return self.fac[n] * self.Ifac[r] * self.Ifac[n-r] % mod

invt = InverseTable(mod, 2*10**5)



def dfs(s,node,parent):
    if len(G[node])>=k: return 0
    elif len(G[node])-s==0: return 1
    else: result=(invt.fac[k-1-s]*invt.Ifac[k-1-s-(len(G[node])-s)])%mod
    for i ,di in enumerate(G[node]):
        if di == parent: continue
        result*=dfs(1,di,node); result%=mod
    
    return result

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

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



factorial = [1]
inverse = [1]
for i in range(1, K + 2):
    factorial.append(factorial[-1] * i % MOD)
    inverse.append(pow(factorial[-1], MOD - 2, MOD))



def nPr(n, r):
    if n < r or r < 0:
        return 0
    elif r == 0:
        return 1
    return factorial[n] * inverse[r] * inverse[n - r] * factorial[r] % MOD


ans = K
stack = [[0, 0]]  
visited = [False] * N
while stack:
    n, depth = stack.pop()
    visited[n] = True

    child = 0
    for to in T[n]:
        if visited[to]:
            continue

        child += 1
        stack.append([to, depth + 1])

    if depth == 0:
        ans *= nPr(K - 1, child)
    else:
        ans *= nPr(K - 2, child)
    ans %= MOD

print(ans % MOD)

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



factorial = [1]
inverse = [1]
for i in range(1, K + 2):
    factorial.append(factorial[-1] * i % MOD)
    inverse.append(pow(factorial[-1], MOD - 2, MOD))



def nPr(n, r):
    if n < r or r < 0:
        return 0
    elif r == 0:
        return 1
    return ((factorial[n] * inverse[r]) % MOD) * (inverse[n - r] * factorial[r] % MOD) % MOD


ans = K
stack = [[0, 0]]  
visited = [False] * N
while stack:
    n, depth = stack.pop()
    visited[n] = True

    child = 0
    for to in T[n]:
        if visited[to]:
            continue

        child += 1
        stack.append([to, depth + 1])

    if depth == 0:
        ans *= nPr(K - 1, child)
    else:
        ans *= nPr(K - 2, child)
    ans %= MOD

print(ans % MOD)

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

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

N, K = lr()
edges = [set() for _ in range(N+1)]
MOD = 10 ** 9 + 7
for _ in range(N-1):
    a, b = lr()
    edges[a].add(b)
    edges[b].add(a)

roots = [None] * (N+1)
roots[1] = 1
que = deque([1])
while que:
    q = que.popleft()
    for next in edges[q]:
        if roots[next] == None:
            roots[next] = q
            que.append(next)

def permutation(n, x):
    
    tmp = 1
    for i in range(n, n-x, -1):
        tmp = (tmp * i) % MOD
    return tmp

def dfs(x):
    global answer
    answer %= MOD
    if x == 1:
        answer *= permutation(K-1, len(edges[x]))
    else:
        answer *= permutation(K-2, len(edges[x])-1)
    for y in edges[x]:
        if y == roots[x]:
            continue
        dfs(y)

answer = K 
dfs(1)
print(answer%MOD)

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    N,K=map(int,input().split())
    edge=[[] for _ in range(N)]
    for _ in range(N-1):
        a,b=map(lambda x:int(x)-1,input().split())
        edge[a].append(b)
        edge[b].append(a)
    stack=[(0,0)]
    ans=K
    used=[False]*N
    while stack:
        v,d=stack.pop()
        i=0
        used[v]=True
        for nv in edge[v]:
            if not used[nv]:
                ans*=K-i-1-min(1,d)
                ans%=MOD
                stack.append((nv,d+1))
                i+=1
    print(ans)
            

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
import sys



def modmal(a,b,mod): 

    return a * b % mod




def moddiv(a,b,mod): 

    return (a * pow(b,mod-2,mod)) % mod




def inverse(a,mod): 
    return pow(a,mod-2,mod)







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


def modnCr(n,r,mod,fac,inv): 

    return fac[n] * inv[n-r] * inv[r] % mod



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

mod = 10**9+7
fac,inv = modfac(max(N,K)+100 , mod)

dic = {}

for i in range(N-1):

    a,b = map(int,input().split())
    a -= 1
    b -= 1

    if a not in dic:
        dic[a] = []
    if b not in dic:
        dic[b] = []

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

ans = K

for i in dic:

    if i == 0:

        ans *= fac[K-1] * inv[K-len(dic[i])-1]
        ans %= mod

        if len(dic[i]) >= K:
            print (0)
            sys.exit()

    else:

        ans *= fac[K-2] * inv[K-len(dic[i])-1]
        ans %= mod

        if len(dic[i]) >= K:
            print (0)
            sys.exit()

print (ans)

Solution (Python):
import sys
from math import factorial
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)

class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

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

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

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

comb = Combination(10 ** 5 + 5)
MOD = 10 ** 9 + 7

def permutations_count(n, r):
    return (comb(n,r) * factorial(r)) % MOD

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

    ans = 1
    q = deque([])
    q.append((0,-1))
    while q:
        s, p = q.popleft()
        for v in edge[s]:
            if p == v:
                continue
            q.append((v,s))
        nk = K if p == -1 else K - 2
        c = len(edge[s]) + 1 if p == -1 else len(edge[s]) - 1
        ans *= permutations_count(nk,c)
        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())
g = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    a, b = map(int, input().split())
    g[a].append(b)
    g[b].append(a)


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

check = [0] * (N + 1)
count = [K - 1] * (N + 1)

check[1] = 1


ans = K
stack = [1]
while stack:
    tmp = stack.pop()
    for next_ in g[tmp]:
        if check[next_] == 1:
            continue
        ans *= count[tmp]
        ans %= MOD
        count[tmp] -= 1
        count[next_] -= 1
        stack.append(next_)
        check[tmp] = 1

print (ans)

Solution (Python):
N,K = map(int,input().split())
AB = [tuple(map(int,input().split())) for i in range(N-1)]
MOD = 10**9+7

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

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 = K
stack = [(0,0)]
visited = [0]*N
while stack:
    v,d = stack.pop()
    visited[v] = 1
    c = 0
    for to in es[v]:
        if visited[to]: continue
        c += 1
        stack.append((to,d+1))
    if c==0: continue
    m = npr(K-1,c) if d==0 else npr(K-2,c)
    ans *= m
    ans %= MOD
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
def main():
    N, K = map(int, input().split())
    Nodes = [set() for _ in range(N)]
    MOD = 10 ** 9 + 7
    for i in range(N - 1):
        a, b = map(int, input().split())
        Nodes[a - 1].add(b - 1)
        Nodes[b - 1].add(a - 1)
    def helper(n, k, f):
        l = len(Nodes[n])
        r = (K - k) 
        j = 1 if k == 0 else 2
        for i in Nodes[n]:
            if i == f:
                continue
            r = r * helper(i, j, n) % MOD
            j += 1
        return r
    for i in range(N):
        if len(Nodes[i]) == 1:
            break
    return helper(i, 0, -1)

print(main())