Buggy python submission (verdict: Time Limit Exceeded):
import sys
from collections import defaultdict, deque
sys.setrecursionlimit(10**6)

def main():
    input = sys.stdin.readline
    MOD = 10**9 + 7
    N, K = map(int, input().split())
    G = defaultdict(list)
    for _ in range(N-1):
        a, b = map(int, input().split())
        a, b = a-1, b-1

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

    visited = [False] * N
    def dfs(n, p, ans):
        cnt = 1
        for p0 in G[p]:
            if visited[p0]:
                cnt += 1
        if n == p:
            cnt -= 1

        ans = (ans * (K - cnt)) % MOD
        visited[n] = True
        for n1 in G[n]:
            if visited[n1]:
                continue

            ans = dfs(n1, n, ans)

        return ans

    return dfs(0, 0, 1)


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


Fixed submission:
import sys
from collections import defaultdict
sys.setrecursionlimit(10**6)

def main():
    input = sys.stdin.readline
    MOD = 10**9 + 7
    N, K = map(int, input().split())
    G = defaultdict(list)
    for _ in range(N-1):
        a, b = map(int, input().split())
        a, b = a-1, b-1

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

    visited = [False] * N
    def dfs(n, ans):
        child = 1
        if n == 0:
            child = 0

        visited[n] = True
        for c in G[n]:
            if visited[c]:
                continue
            ans = (ans * (K - 1 - child)) % MOD
            ans = dfs(c, ans)
            child += 1

        return ans

    return dfs(0, K)


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

Buggy python submission (verdict: Time Limit Exceeded):
import sys
from collections import defaultdict, deque
sys.setrecursionlimit(10**6)

def main():
    input = sys.stdin.readline
    MOD = 10**9 + 7
    N, K = map(int, input().split())
    G = defaultdict(list)
    for _ in range(N-1):
        a, b = map(int, input().split())
        a, b = a-1, b-1

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

    visited = [False] * N
    def dfs(n, p, ans):
        cnt = 1
        for p0 in G[p]:
            if visited[p0]:
                cnt += 1
        if n == p:
            cnt -= 1

        ans = (ans * (K - cnt)) % MOD
        visited[n] = True
        for n1 in G[n]:
            if visited[n1]:
                continue

            ans = dfs(n1, n, ans)

        return ans

    return dfs(0, 0, 1)


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


Fixed submission:
import sys
from collections import defaultdict
sys.setrecursionlimit(10**6)

def main():
    input = sys.stdin.readline
    MOD = 10**9 + 7
    N, K = map(int, input().split())
    G = defaultdict(list)
    for _ in range(N-1):
        a, b = map(int, input().split())
        a, b = a-1, b-1

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

    visited = [False] * N
    def dfs(n, ans):
        child = 1
        if n == 0:
            child = 0

        visited[n] = True
        for c in G[n]:
            if visited[c]:
                continue
            ans = (ans * (K - 1 - child)) % MOD
            ans = dfs(c, ans)
            child += 1

        return ans

    return dfs(0, K)


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