Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict
import sys
sys.setrecursionlimit(10 ** 7)
graph = defaultdict(list)

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

mod = 10 ** 9 + 7


def dfs(fro, to, f):
    caseNum = f
    colorNum = K - 1 if f == K else K - 2
    for u in graph[fro]:
        if u == to:
            continue
        pat = dfs(u, fro, colorNum)
        if pat == 0:
            caseNum = 0
            break
        caseNum = caseNum * pat % mod
        colorNum -= 1
    return caseNum


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

Fixed submission:
import sys

stdin = sys.stdin

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

sys.setrecursionlimit(100005)

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


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


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

Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict
import sys
sys.setrecursionlimit(10 ** 7)
graph = defaultdict(list)

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

mod = 10 ** 9 + 7


def dfs(K, fro, to):
    if fro == -1:
        colorNum = K-1
    else:
        colorNum = K-2
    if K < len(graph[fro]):
        return 0
    else:
        caseNum = 1
        for e in graph[fro]:
            if e == fro:
                continue
            caseNum *= colorNum
            colorNum -= 1
            caseNum %= mod
        for e in graph[fro]:
            if e == fro:
                continue
            caseNum *= dfs(K, e, fro)
            caseNum %= mod
    return caseNum


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

Fixed submission:
import sys

stdin = sys.stdin

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

sys.setrecursionlimit(100005)

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


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


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

Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict
import sys
sys.setrecursionlimit(10 ** 7)
graph = defaultdict(list)

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

mod = 10 ** 9 + 7


def dfs(K, fro, to):
    if fro == -1:
        colorNum = K-1
    else:
        colorNum = K-2
    if K < len(graph[fro]):
        return 0
    else:
        caseNum = 1
        for e in graph[fro]:
            if e == fro:
                continue
            caseNum *= colorNum
            colorNum -= 1
            caseNum %= mod
        for e in graph[fro]:
            if e == fro:
                continue
            caseNum *= dfs(K, e, fro)
            caseNum %= mod
    return caseNum


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

Fixed submission:
import sys

stdin = sys.stdin

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

sys.setrecursionlimit(100005)

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


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


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