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

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

class FactInvMOD:
    """ 階乗たくさん使う時用のテーブル準備 """

    def __init__(self, MAX, MOD):
        """ MAX：階乗に使う数値の最大以上まで作る """
        
        MAX += 1
        self.MAX = MAX
        self.MOD = MOD

        
        factorial = [1] * MAX
        factorial[0] = factorial[1] = 1
        for i in range(2, MAX):
            factorial[i] = factorial[i-1] * i % MOD
        
        inverse = [1] * MAX
        
        inverse[MAX-1] = pow(factorial[MAX-1], MOD-2, MOD)
        for i in range(MAX-2, 0, -1):
            
            inverse[i] = inverse[i+1] * (i+1) % MOD
        self.fact = factorial
        self.inv = inverse
    
    def nCr(self, n, r):
        """ 組み合わせの数 (必要な階乗と逆元のテーブルを事前に作っておく) """
        if n < r: return 0
        
        r = min(r, n-r)
        
        numerator = self.fact[n]
        
        denominator = self.inv[r] * self.inv[n-r] % self.MOD
        return numerator * denominator % self.MOD

    def nPr(self, n, r):
        """ 順列 """
        if n < r: return 0
        return self.fact[n] * self.inv[n-r] % self.MOD

N,K=MAP()
nodes=[[] for i in range(N)]
for i in range(N-1):
    a,b=MAP()
    nodes[a-1].append(b-1)
    nodes[b-1].append(a-1)

fim=FactInvMOD(max(N, K), MOD)

ans=1
def rec(u, prev):

    global ans
    
    cldcnt=len(nodes[u])
    
    if u==0:
        ans*=fim.nPr(K, cldcnt+1)
    
    else:
        
        cldcnt-=1
        ans*=fim.nPr(K-2, cldcnt)
    ans%=MOD
    for v in nodes[u]:
        if v!=prev:
            rec(v, u)

rec(0, -1)
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 9)
MOD = 10 ** 9 + 7

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

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


dic = {}


def Perm(n, k):
    if (n, k) in dic:
        return dic[(n, k)]
    ans = 1
    for i in range(n - k + 1, n + 1):
        ans *= i
        ans %= MOD
    dic[(n, k)] = ans
    return ans


def dfs(g, p):
    ans = Perm(K - 2, len(P[p]) - 1)
    for c in P[p]:
        if not c == g:
            ans *= dfs(p, c)
            ans %= MOD
    return ans


ans = Perm(K, len(P[0]) + 1)
for c in P[0]:
    ans *= dfs(0, c)
    ans %= MOD

print(ans)

Solution (Python):
import sys
s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in ss]
ss2nnn = lambda ss: [s2nn(s) for s in ss]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2sss = lambda n: [list(sys.stdin.readline().rstrip()) for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

MOD = int(1e+9) + 7
from collections import deque  

def perm(n, k):
    r = 1
    for i in range(n, n-k, -1):
        r = (r * i) % MOD
    return r

def main():
    N, K = i2nn()
    edges = ii2nnn(N-1)
    
    T = [[] for _ in range(N+1)]
    B = [False] * (N+1)
    for a, b in edges:
        T[a].append(b)
        T[b].append(a)
    
    n = K
    q = deque()
    i = 1
    B[i] = True
    k = 0
    for j in T[i]:
        q.append(j)
        B[j] = True
        k += 1
    n = (n * perm(K-1, k)) % MOD
    while q:
        i = q.pop()
        k = 0
        for j in T[i]:
            if B[j] == False:
                q.append(j)
                B[j] = True
                k += 1
        n = (n * perm(K-2, k)) % MOD
    print(n)

main()

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

class FactInvMOD:
    """ 階乗たくさん使う時用のテーブル準備 """

    def __init__(self, MAX, MOD):
        """ MAX：階乗に使う数値の最大以上まで作る """
        
        MAX += 1
        self.MAX = MAX
        self.MOD = MOD

        
        factorial = [1] * MAX
        factorial[0] = factorial[1] = 1
        for i in range(2, MAX):
            factorial[i] = factorial[i-1] * i % MOD
        
        inverse = [1] * MAX
        
        inverse[MAX-1] = pow(factorial[MAX-1], MOD-2, MOD)
        for i in range(MAX-2, 0, -1):
            
            inverse[i] = inverse[i+1] * (i+1) % MOD
        self.fact = factorial
        self.inv = inverse
    
    def nCr(self, n, r):
        """ 組み合わせの数 (必要な階乗と逆元のテーブルを事前に作っておく) """
        if n < r: return 0
        
        r = min(r, n-r)
        
        numerator = self.fact[n]
        
        denominator = self.inv[r] * self.inv[n-r] % self.MOD
        return numerator * denominator % self.MOD

    def nPr(self, n, r):
        """ 順列 """
        if n < r: return 0
        return self.fact[n] * self.inv[n-r] % self.MOD

N,K=MAP()
nodes=[[] for i in range(N)]
for i in range(N-1):
    a,b=MAP()
    nodes[a-1].append(b-1)
    nodes[b-1].append(a-1)

fim=FactInvMOD(max(N, K), MOD)

visited=[False]*N
ans=1
def rec(u):
    if visited[u]:
        return
    visited[u]=True
    global ans
    
    cldcnt=len(nodes[u])
    
    if u==0:
        ans*=fim.nPr(K, cldcnt+1)
    
    else:
        
        cldcnt-=1
        ans*=fim.nPr(K-2, cldcnt)
    ans%=MOD
    for v in nodes[u]:
        rec(v)

rec(0)
print(ans)

Solution (Python):
import sys

input = sys.stdin.readline
N, K = map(int, input().split())

MOD = 10 ** 9 + 7

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

def P(n, r, MOD):
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret %= MOD
    return ret

def dfs():
    used = [0] * N
    ret = K
    stuck = [0]
    while stuck:
        v = stuck.pop()
        child_number = sum(not used[i] for i in edges[v])
        if not child_number:
            used[v] = True
            continue
        ret *= P(K - 2 + (v == 0), child_number, MOD)
        ret %= MOD
        used[v] = True
        for u in edges[v]:
            if used[u]:
                continue
            stuck.append(u)
    return ret

print(dfs())

Solution (Python):

import sys
from operator import itemgetter

from fractions import gcd

from math import ceil, floor

from copy import deepcopy

from itertools import accumulate






from collections import Counter
import math
from functools import reduce
sys.setrecursionlimit(200000)

input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def li(): return list(input().rstrip())
def debug(*x): print("debug:", *x, file=sys.stderr)








MOD = 10**9 + 7



class Modint():
    '''
    自動でMODで割った余りを計算してくれる整数。MODは素数である必要があり，デフォルトは10**9+7。

    Parameters
    ----------
        n (int) : Modintの初期値
        MOD=10^9+7 (int) : 余りを計算するMOD。素数である必要がある。

    Methods
    ----------
        inverse(n: int) -> Modint
            n の逆元を返す。
    '''

    def __init__(self, n: int, mod=MOD):
        if n >= 0:
            self.n = n % mod
        else:
            self.n = (mod - (-n) % mod) % mod
        self.mod = mod

    def __eq__(self, other):
        return self.n == int(other)

    def __ne__(self, other):
        return not self == other

    def __neg__(self):
        return self.__class__(-self.n)

    def __str__(self):
        return str(self.n)

    def __int__(self):
        return self.n

    def __iadd__(self, other):
        self.n += int(other)
        self.n %= self.mod
        return self

    def __radd__(self, other):
        return self.__add__(other)

    def __isub__(self, other):
        self.n -= int(other)
        self.n %= self.mod
        return self

    def __rsub__(self, other):
        return self.__sub__(other)

    def __imul__(self, other):
        self.n = self.n * int(other) % self.mod
        return self

    def __rmul__(self, other):
        return self.__mul__(other)

    def inverse(self):
        '''
        フェルマーの小定理を考えると，MOD-2乗することでMODでの逆元を求めることができる。これは組み込み関数のpowを使うと十分に早い（O(log MOD)）。
        '''
        return self.__class__(pow(self.n, self.mod - 2, self.mod))

    def __ifloordiv__(self, other):
        self *= pow(int(other), self.mod - 2, self.mod)
        return self

    def __rfloordiv__(self, other):
        return self.__class__(other).__floordiv__(self)

    def __add__(self, other):
        return self.__class__(self.n + int(other))

    def __sub__(self, other):
        return self.__class__(self.n - int(other))

    def __mul__(self, other):
        return self.__class__(self.n * int(other))

    def __floordiv__(self, other):
        return self.__class__(self.n * Modint(int(other)).inverse())

    
    
    
    

    
    
    
    
    
    
    
    
    

    
    
    
    
    
    
    


COMBINATION_MAX = 2 * 10**5


class Combination():
    def __init__(self, sz=COMBINATION_MAX):
        '''
        Nまでの階乗とその逆元（割り算用）を計算しておく。前処理にO(N)，P, C, Hそれぞれの計算はO(1)。N = 200000なら割と余裕で通る。
        '''
        self._fact = [Modint(0)] * (sz + 1)
        self._rfact = [Modint(0)] * (sz + 1)
        self._fact[0] = Modint(1)
        self._rfact[sz] = Modint(1)
        for i in range(1, sz + 1):
            self._fact[i] = self._fact[i - 1] * Modint(i)
        self._rfact[sz] = self._fact[sz].inverse()
        for i in range(sz - 1, -1, -1):
            self._rfact[i] = self._rfact[i + 1] * Modint(i + 1)

    def fact(self, k: int) -> int:
        """階乗の計算"""
        return self._fact[k]

    def rfact(self, k: int) -> int:
        """階乗の逆元の計算"""
        return self._rfact[k]

    def P(self, n: int, k: int) -> Modint:
        '''
        nPkの値を返す。nはあらかじめ前処理されたN以下でないとダメ

        Parameters
        ----------
            n (int) : nPkのn (0<=n<=N)
            k (int) : nPkのk （0<=k<=n）

        Returns
        ----------
            Modint : nPkをModint型で返す。Modintに依存。
        '''
        if k < 0 or n < k:
            return Modint(0)
        return self._fact[n] * self._rfact[n - k]

    def C(self, n: int, k: int) -> Modint:
        '''
        nCkの値を返す。nはあらかじめ前処理されたN以下でないとダメ

        Parameters
        ----------
            n (int) : nCkのn(0<=n<=N)
            k (int) : nCkのk（0<=k<=n）

        Returns
        ----------
            Modint : nCkをModint型で返す。Modintに依存。
        '''
        if k < 0 or n < k:
            return Modint(0)
        if n - k < k:
            k = n - k
        return self._fact[n] * self._rfact[k] * self._rfact[n - k]

    def H(self, n: int, k: int) -> Modint:
        '''
        nHkの値を返す。nはあらかじめ前処理された n+k-1 以下でないとダメ

        ちなみにnHkはn個の区別できないものをk個の箱に分けるパターンの数で，結局n+k-1Cnになる。

        Parameters
        ----------
            n (int) : nHkのn(0<=n<=N)
            k (int) : nHkのk（0<=k<=n）

        Returns
        ----------
            Modint : nHkをModint型で返す。Modintに依存。
        '''
        if n < 0 or k < 0:
            return Modint(0)
        elif k == 0:
            return Modint(1)
        return self.C(n + k - 1, k)




def solve(N: int, K: int, a: "List[int]", b: "List[int]"):
    comb = Combination(110000)
    G = [[] for _ in range(N)]
    for i in range(N - 1):
        G[a[i]-1].append(b[i]-1)
        G[b[i]-1].append(a[i]-1)
    res = Modint(1)

    def dfs(v, p, depth):
        nonlocal res
        cnt = 0
        for nv in G[v]:
            if nv == p:
                continue
            cnt += 1
            dfs(nv, v, depth + 1)
        
        if depth == 0:
            res *= comb.P(K - 1, cnt)
        else:
            res *= comb.P(K - 2, cnt)

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


def iterate_tokens():
    for line in sys.stdin:
        for word in line.split():
            yield word


def main():
    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):
import sys
from collections import deque
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return list(map(int, sys.stdin.readline().split()))

def main():
    n, k = LI()
    g = [[] for i in range(n+1)]
    for i in range(n-1):
        a, b = LI()
        g[a].append(b)
        g[b].append(a)

    s = 1
    Q = deque([s])
    ans = k
    Qappend = Q.append
    searched = [0] * (n+1)
    searched[s] = 1
    while len(Q) != 0:
        v = Q.popleft()
        if v == s:
            cand = k - 1
        else:
            cand = k - 2
        for i in g[v]:
            if searched[i] == 1:
                continue
            searched[i] = 1
            ans = ans * cand % MOD
            cand -= 1
            Qappend(i)
    print(ans % MOD)


if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque

N, K = list(map(int,input().split()))
ab = [list(map(int, input().split())) for _ in range(N - 1)]
MOD = 1000000007
if N == 1:
    print(K)
    exit()

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

for i in range(N - 1):
    tree[ab[i][0] - 1].append(ab[i][1] - 1)
    tree[ab[i][1] - 1].append(ab[i][0] - 1)


ans = K * (K - 1) % MOD

first = 0
for i in range(N):
    if len(tree[i]) == 1:
        first = i
        break

q = deque([[first, tree[first][0]]])

while q:
    parent, child = q.pop()
    count = 2
    for i in range(len(tree[child])):
        if tree[child][i] != parent:
            q.append([child, tree[child][i]])
            ans = ans * (K - count) % MOD
            count += 1

print(ans)

Solution (Python):
import sys
from collections import deque
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return list(map(int, sys.stdin.readline().split()))

def main():
    n, k = LI()
    g = [[] for i in range(n+1)]
    for i in range(n-1):
        a, b = LI()
        g[a].append(b)
        g[b].append(a)

    s = 1
    Q = deque([s])
    ans = k
    Qappend = Q.append
    searched = [0] * (n+1)
    searched[s] = 1
    while len(Q) != 0:
        v = Q.popleft()
        if v == s:
            cand = k - 1
        else:
            cand = k - 2
        for i in g[v]:
            if searched[i] == 1:
                continue
            searched[i] = 1
            ans = ans * cand % MOD
            cand -= 1
            Qappend(i)
    print(ans % MOD)


if __name__ == "__main__":
    main()

Solution (Python):
def e_virus_tree_2(N, K, Edges, MOD=10**9 + 7):
    import sys
    sys.setrecursionlimit(10**6)
    
    graph = [[] for _ in range(N)]
    for a, b in Edges:
        graph[b - 1].append(a - 1)
        graph[a - 1].append(b - 1)

    def dfs(color, graph, current, parent):
        can_use_color_num = K - 1 if parent == -1 else K - 2

        if color < len(graph[current]):
            return 0  

        
        case_num = 1
        for child in graph[current]:
            if child == parent:
                continue
            case_num *= can_use_color_num
            case_num %= MOD
            can_use_color_num -= 1
        for child in graph[current]:
            if child == parent:
                continue
            case_num *= dfs(color, graph, child, current)
            case_num %= MOD
        return case_num

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

N, K = [int(i) for i in input().split()]
Edges = [[int(i) for i in input().split()] for j in range(N - 1)]
print(e_virus_tree_2(N, K, Edges))

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

from collections import deque

N,K = map(int, input().split())
G = [[] for i in range(N)]
for i in range(N-1):
    
    u,v = map(int,input().split())
    G[u-1].append((v-1))
    G[v-1].append((u-1))



used = [False] * N
used[0] = True
mod = 10**9 + 7
cnt = 0
ans = K
def dfs(G, i, v):
    global cnt
    global ans 
    
    used[v] = True
    cnt += 1
    numv = 0
    for next_v in G[v]:
        
        if used[next_v]: continue
        numv += 1
        ans %= mod
        if i <= 1:
            ans *= K-i-numv
        else:
            ans *= K - 1 - numv
        
        ans %= mod
        dfs(G,i+1, next_v)



dfs(G,0,0)
print(ans%mod)

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class Mod:
    def __init__(self, m):
        self.m = m

    def add(self, a, b):
        return (a + b) % self.m

    def sub(self, a, b):
        return (a - b) % self.m

    def mul(self, a, b):
        return ((a % self.m) * (b % self.m)) % self.m

    def div(self, a, b):
        return self.mul(a, pow(b, self.m-2, self.m))

    def pow(self, a, b):
        return pow(a, b, self.m)


@mt
def slv(N, K, AB):
    M = Mod(10**9+7)
    def P(n, k):
        ret = 1
        for i in range(n, n-k, -1):
            ret = M.mul(ret, i)
        return ret
    
    g = defaultdict(list)
    for a, b in AB:
        g[a].append(b)
        g[b].append(a)
    
    s = 1
    q = g[s][:]
    done = set([s]) | set(q)
    ans = K
    ans = M.mul(ans, P(K-1, len(g[s])))
    while q:
        u = q.pop()
        for v in g[u]:
            if v not in done:
                done.add(v)
                q.append(v)
        c = len(g[u])-1
        ans = M.mul(ans, P(K-2, c))
    return ans


def main():
    N, K = read_int_n()
    AB = [read_int_n() for _ in range(N-1)]
    print(slv(N, K, AB))


if __name__ == '__main__':
    main()

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class Mod:
    def __init__(self, m):
        self.m = m

    def add(self, a, b):
        return (a + b) % self.m

    def sub(self, a, b):
        return (a - b) % self.m

    def mul(self, a, b):
        return ((a % self.m) * (b % self.m)) % self.m

    def div(self, a, b):
        return self.mul(a, pow(b, self.m-2, self.m))

    def pow(self, a, b):
        return pow(a, b, self.m)


@mt
def slv(N, K, AB):
    M = Mod(10**9+7)
    def P(n, k):
        ret = 1
        for i in range(n, n-k, -1):
            ret = M.mul(ret, i)
        return ret
    
    g = defaultdict(list)
    for a, b in AB:
        g[a].append(b)
        g[b].append(a)
    
    s = 1
    q = g[s][:]
    done = set([s]) | set(q)
    ans = K
    ans = M.mul(ans, P(K-1, len(g[s])))
    while q:
        u = q.pop()
        for v in g[u]:
            if v not in done:
                done.add(v)
                q.append(v)
        c = len(g[u])-1
        ans = M.mul(ans, P(K-2, c))
    return ans


def main():
    N, K = read_int_n()
    AB = [read_int_n() for _ in range(N-1)]
    print(slv(N, K, AB))


if __name__ == '__main__':
    main()

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class Mod:
    def __init__(self, m):
        self.m = m

    def add(self, a, b):
        return (a + b) % self.m

    def sub(self, a, b):
        return (a - b) % self.m

    def mul(self, a, b):
        return ((a % self.m) * (b % self.m)) % self.m

    def div(self, a, b):
        return self.mul(a, pow(b, self.m-2, self.m))

    def pow(self, a, b):
        return pow(a, b, self.m)


@mt
def slv(N, K, AB):
    M = Mod(10**9+7)
    def P(n, k):
        ret = 1
        for i in range(n, n-k, -1):
            ret = M.mul(ret, i)
        return ret
    
    g = defaultdict(list)
    for a, b in AB:
        g[a].append(b)
        g[b].append(a)
    
    q = [1]
    done = set()
    ans = K
    while q:
        u = q.pop()
        
        for v in g[u]:
            if v not in done:
                done.add(v)
                q.append(v)
        c = len(g[u])-1
        if u == 1:
            c += 1
        
        done.add(u)
        if u == 1:
            ans = M.mul(ans, P(K-1, c))
        else:
            ans = M.mul(ans, P(K-2, c))
    return ans


def main():
    N, K = read_int_n()
    AB = [read_int_n() for _ in range(N-1)]
    print(slv(N, K, AB))


if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
MOD = 10**9+7

def perm(num, col):
	global ans
	for i in range(num):
		ans *= col-i
		ans %= MOD
	return

n, k = map(int, input().split())
adj = [[] for _ in range(n)]
for _ in range(n-1):
	a, b = map(int, input().split())
	adj[a-1].append(b-1)
	adj[b-1].append(a-1)
par = [-1 for _ in range(n)]
def dfs1(x, p):
	for v in adj[x]:
		if v == p:
			continue
		par[v] = x
		dfs1(v, x)
	return
dfs1(0, -1)

ans = k
perm(len(adj[0]), k-1)

def dfs2(x):
	if len(adj[x]) == 1:
		return
	else:
		perm(len(adj[x])-1, k-2)
		for v in adj[x]:
			if v == par[x]:
				continue
			else:
				dfs2(v)
		return

for v in adj[0]:
	dfs2(v)
print(ans)

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class Mod:
    def __init__(self, m):
        self.m = m

    def add(self, a, b):
        return (a + b) % self.m

    def sub(self, a, b):
        return (a - b) % self.m

    def mul(self, a, b):
        return ((a % self.m) * (b % self.m)) % self.m

    def div(self, a, b):
        return self.mul(a, pow(b, self.m-2, self.m))

    def pow(self, a, b):
        return pow(a, b, self.m)


@mt
def slv(N, K, AB):
    M = Mod(10**9+7)
    def P(n, k):
        ret = 1
        for i in range(n, n-k, -1):
            ret = M.mul(ret, i)
        return ret
    
    g = defaultdict(list)
    for a, b in AB:
        g[a].append(b)
        g[b].append(a)
    
    q = [1]
    done = set()
    ans = K
    while q:
        u = q.pop()
        
        for v in g[u]:
            if v not in done:
                done.add(v)
                q.append(v)
        c = len(g[u])-1
        if u == 1:
            c += 1
        
        done.add(u)
        if u == 1:
            ans = M.mul(ans, P(K-1, c))
        else:
            ans = M.mul(ans, P(K-2, c))
    return ans


def main():
    N, K = read_int_n()
    AB = [read_int_n() for _ in range(N-1)]
    print(slv(N, K, AB))


if __name__ == '__main__':
    main()

Solution (Python):
import operator as op
from functools import reduce
 
def npr(n, r):
    numer = 1
    for k in range(r):
        numer = numer * (n - k)
        numer %= q
    return numer


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

child_num = [0 for i in range(N)]
for k in range(N - 1):
    a, b = list(map(int, input().split()))
    a -= 1
    b -= 1
    child_num[a] += 1
    child_num[b] += 1

for i in range(1, N):
    child_num[i] -= 1


min_child = min(child_num)
if K < min_child:
    print(0)
else:
    ans = (K * npr(K - 1, child_num[0])) % q
    for i in range(1, N):
        val = npr(K - 2, child_num[i]) % q
        ans = (ans * val) % q
    print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(1000000000)
N, K = list(map(int,input().split()))
ab = [list(map(int, input().split())) for _ in range(N - 1)]
MOD = 1000000007
if N == 1:
    print(K)
    exit()

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

for i in range(N - 1):
    tree[ab[i][0] - 1].append(ab[i][1] - 1)
    tree[ab[i][1] - 1].append(ab[i][0] - 1)


ans = K * (K - 1) % MOD

def f(x, y):
    global ans
    count = 2
    for i in range(len(tree[y])):
        if tree[y][i] != x:
            f(y, tree[y][i])
            ans = ans * (K - count) % MOD
            count += 1


first = 0
for i in range(N):
    if len(tree[i]) == 1:
        first = i
        break
f(first, tree[first][0])


print(ans)

Solution (Python):
from collections import deque

MOD = 1000000007
n, k = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(n-1)]
edges = [set() for _ in range(n)]
visited = [False for _ in range(n)]
for a, b in AB:
    edges[a-1].add(b-1)
    edges[b-1].add(a-1)

def perm(n, r):
    if n < r or r < 0:
        return 0
    tmp = 1
    for i in range(n, n-r, -1):
        tmp *= i
        tmp %= MOD
    return tmp

q = deque([0])
visited[0] = True
first = True
ans = k
while q:
    v = q.popleft()
    visited[v] = True
    children = list(filter(lambda x: not visited[x], edges[v]))
    if first:
        ans *= perm(k-1, len(children))
        ans %= MOD
        first = False
    else:
        ans *= perm(k-2, len(children))
        ans %= MOD
    q.extend(children)
print(ans)

Solution (Python):
from collections import deque


n, k = map(int, input().split())
info = [list(map(int, input().split())) for i in range(n-1)]
MOD = 10**9 + 7
tree = [[] for i in range(n)]
for i in range(n-1):
    tree[info[i][0] - 1].append(info[i][1] - 1)
    tree[info[i][1] - 1].append(info[i][0] - 1)

visited = [-1] * n
q = deque([0])
visited[0] = k

while q:
    pos = q.pop()
    cnt = k - 1
    for i in tree[pos]:
        if visited[i] != -1:
            cnt -= 1
    for i in tree[pos]:
        if visited[i] == -1:
            if cnt == 0:
                print(0)
                exit()
            visited[i] = cnt
            cnt -= 1
            q.append(i)
ans = 1
for i in range(n):
    ans *= visited[i]
    ans %= MOD
print(ans)

Solution (Python):
from collections import deque

MOD = 1000000007
n, k = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(n-1)]
edges = [set() for _ in range(n)]
visited = [False for _ in range(n)]
for a, b in AB:
    edges[a-1].add(b-1)
    edges[b-1].add(a-1)

upper = max(n, k)
fact = [1] * (upper+1)
fact_inv = [1] * (upper+1)
for i in range(1, upper+1):
    fact[i] = fact[i-1] * i % MOD
fact_inv[upper] = pow(fact[upper], MOD-2, MOD)
for i in range(upper-1, 0, -1):
    fact_inv[i] = fact_inv[i+1] * (i+1) % MOD
def perm(n, r):
    if n < r or r < 0:
        return 0
    return fact[n] * fact_inv[n-r] % MOD

q = deque([0])
visited[0] = True
first = True
ans = k
while q:
    v = q.popleft()
    visited[v] = True
    children = list(filter(lambda x: not visited[x], edges[v]))
    if first:
        ans *= perm(k-1, len(children))
        ans %= MOD
        first = False
    else:
        ans *= perm(k-2, len(children))
        ans %= MOD
    q.extend(children)
print(ans)