Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
from math import factorial

def perm(n, r):
    if n >= r:
        return factorial(n) // factorial(n - r)
    else:
        return 0

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)
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)


Fixed submission:
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)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
from math import factorial

def perm(n, r):
    if n >= r:
        return factorial(n) // factorial(n - r)
    else:
        return 0

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)
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)


Fixed submission:
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)