Buggy python submission (verdict: Runtime Error):
mod = 10 ** 9 + 7


def p(n, r):
    if n < r:
        return 0
    return fact[n] * invs[n - r] % mod


def dfs(v, bf):
    global ans
    if v == 0:
        ans *= p(k, len(es[v]) + 1)
        ans %= mod
    else:
        ans *= p(k - 2, len(es[v]) - 1)
        ans %= mod

    for nv in es[v]:
        if nv == bf: continue
        dfs(nv, v)


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

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

fact = [1]
for i in range(1, k + 1):
    fact.append(fact[-1] * i % mod)

invs = [None] * (k + 1)
invs[k] = pow(fact[-1], mod - 2, mod)
for i in range(k - 1, -1, -1):
    invs[i] = invs[i + 1] * (i + 1) % mod

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


Fixed submission:
import sys

sys.setrecursionlimit(10 ** 6)

mod = 10 ** 9 + 7

input = sys.stdin.readline


def rec(v, bf):
    global ans
    gs[v] += 1
    gs[bf] += 1
    ans = ans * (K - gs[bf]) % mod
    for nv in es[v]:
        if nv == bf: continue
        rec(nv, v)
    return


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

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

gs = [0] * (N + 1)
gs[0] = -1
gs[N] = -1

ans = 1

rec(0, N)
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import sys

sys.setrecursionlimit(10 ** 6)

mod = 10 ** 9 + 7

input = sys.stdin.readline


def rec(v, bf):
    global ans
    gs[v] += 1
    gs[bf] += 1
    ans = ans * (K - gs[bf]) % mod
    for nv in es[v]:
        if nv == bf: continue
        rec(nv, v)
    return


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

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

gs = [0] * (N + 1)
gs[0] = -1
gs[N] = -1

ans = 1

rec(0, N)
print(ans)


Fixed submission:
import sys

sys.setrecursionlimit(10 ** 6)

mod = 10 ** 9 + 7

input = sys.stdin.readline


def rec(v, bf):
    global ans
    gs[v] += 1
    gs[bf] += 1
    ans = ans * (K - gs[bf]) % mod
    for nv in es[v]:
        if nv == bf: continue
        rec(nv, v)
    return


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

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

gs = [0] * (N + 1)
gs[0] = -1
gs[N] = -1

ans = 1

rec(0, N)
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import sys

sys.setrecursionlimit(10 ** 6)

mod = 10 ** 9 + 7

input = sys.stdin.readline

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

es = [[] for _ in range(N)]
g = [0] * N
for _ in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    es[a].append(b)
    g[a] += 1
    es[b].append(a)
    g[b] += 1

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


def rec(v, bf):
    global ans
    visited[v] = True
    gs[v] += 1
    gs[bf] += 1
    ans = ans * (K - gs[bf]) % mod
    for nv in es[v]:
        if not visited[nv]:
            rec(nv, v)
    return


rec(0, N)
print(ans)
# print(gs)


Fixed submission:
import sys

sys.setrecursionlimit(10 ** 6)

mod = 10 ** 9 + 7

input = sys.stdin.readline


def rec(v, bf):
    global ans
    gs[v] += 1
    gs[bf] += 1
    ans = ans * (K - gs[bf]) % mod
    for nv in es[v]:
        if nv == bf: continue
        rec(nv, v)
    return


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

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

gs = [0] * (N + 1)
gs[0] = -1
gs[N] = -1

ans = 1

rec(0, N)
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import sys

sys.setrecursionlimit(10 ** 6)

mod = 10 ** 9 + 7

input = sys.stdin.readline

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

es = [[] for _ in range(N)]
g = [0] * N
for _ in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    es[a].append(b)
    g[a] += 1
    es[b].append(a)
    g[b] += 1

s = -1
b = -1
for i, gg in enumerate(g):
    if gg > b:
        b = gg
        s = i

gs = [0] * (N + 1)
gs[s] = -1
gs[N] = -1
visited = [False] * N
ans = 1


def rec(v, bf):
    global ans
    visited[v] = True
    gs[v] += 1
    gs[bf] += 1
    ans = ans * (K - gs[bf]) % mod
    for nv in es[v]:
        if not visited[nv]:
            rec(nv, v)
    return


rec(s, N)
print(ans)
# print(gs)


Fixed submission:
import sys

sys.setrecursionlimit(10 ** 6)

mod = 10 ** 9 + 7

input = sys.stdin.readline


def rec(v, bf):
    global ans
    gs[v] += 1
    gs[bf] += 1
    ans = ans * (K - gs[bf]) % mod
    for nv in es[v]:
        if nv == bf: continue
        rec(nv, v)
    return


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

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

gs = [0] * (N + 1)
gs[0] = -1
gs[N] = -1

ans = 1

rec(0, N)
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import sys

sys.setrecursionlimit(10 ** 6)

mod = 10 ** 9 + 7

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

es = [[] for _ in range(N)]
g = [0] * N
for _ in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    es[a].append(b)
    g[a] += 1
    es[b].append(a)
    g[b] += 1

s = -1
b = -1
for i, gg in enumerate(g):
    if gg > b:
        b = gg
        s = i

gs = [0] * (N + 1)
gs[s] = -1
gs[N] = -1
visited = [False] * N
ans = 1


def rec(v, bf):
    global ans
    if visited[v]:
        return
    visited[v] = True
    gs[v] += 1
    gs[bf] += 1
    ans *= K - gs[bf]
    ans %= mod

    for nv in es[v]:
        if not visited[nv]:
            rec(nv, v)
    return


rec(s, N)
print(ans)

# print(gs)


Fixed submission:
import sys

sys.setrecursionlimit(10 ** 6)

mod = 10 ** 9 + 7

input = sys.stdin.readline


def rec(v, bf):
    global ans
    gs[v] += 1
    gs[bf] += 1
    ans = ans * (K - gs[bf]) % mod
    for nv in es[v]:
        if nv == bf: continue
        rec(nv, v)
    return


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

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

gs = [0] * (N + 1)
gs[0] = -1
gs[N] = -1

ans = 1

rec(0, N)
print(ans)

Buggy python submission (verdict: Runtime Error):
mod = 10 ** 9 + 7

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

es = [[] for _ in range(N)]
g = [0] * N
for _ in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    es[a].append(b)
    g[a] += 1
    es[b].append(a)
    g[b] += 1

s = -1
b = -1
for i, gg in enumerate(g):
    if gg > b:
        b = gg
        s = i
if b == -1 or s == -1:
    print(K)
    exit()

gs = [0] * (N + 1)
gs[s] = -1
gs[N] = -1
visited = [False] * N
ans = 1


def rec(v, bf):
    global ans
    if visited[v]:
        return
    visited[v] = True
    gs[v] += 1
    gs[bf] += 1
    ans *= K - gs[bf]
    ans %= mod

    for nv in es[v]:
        if not visited[nv]:
            rec(nv, v)
    return


rec(s, N)
print(ans)

# print(gs)


Fixed submission:
import sys

sys.setrecursionlimit(10 ** 6)

mod = 10 ** 9 + 7

input = sys.stdin.readline


def rec(v, bf):
    global ans
    gs[v] += 1
    gs[bf] += 1
    ans = ans * (K - gs[bf]) % mod
    for nv in es[v]:
        if nv == bf: continue
        rec(nv, v)
    return


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

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

gs = [0] * (N + 1)
gs[0] = -1
gs[N] = -1

ans = 1

rec(0, N)
print(ans)

Buggy python submission (verdict: Runtime Error):
mod = 10 ** 9 + 7

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

es = [[] for _ in range(N)]
g = [0] * N
for _ in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    es[a].append(b)
    g[a] += 1
    es[b].append(a)
    g[b] += 1

s = -1
b = -1
for i, gg in enumerate(g):
    if gg > b:
        b = gg
        s = i
if b == -1 or s == -1:
    print(1)
    exit()

gs = [0] * (N + 1)
gs[s] = -1
gs[N] = -1
visited = [False] * N
ans = 1


def rec(v, bf):
    global ans
    if visited[v]:
        return
    visited[v] = True
    gs[v] += 1
    gs[bf] += 1
    ans *= K - gs[bf]
    ans %= mod

    for nv in es[v]:
        if not visited[nv]:
            rec(nv, v)
    return


rec(s, N)
print(ans)

# print(gs)


Fixed submission:
import sys

sys.setrecursionlimit(10 ** 6)

mod = 10 ** 9 + 7

input = sys.stdin.readline


def rec(v, bf):
    global ans
    gs[v] += 1
    gs[bf] += 1
    ans = ans * (K - gs[bf]) % mod
    for nv in es[v]:
        if nv == bf: continue
        rec(nv, v)
    return


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

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

gs = [0] * (N + 1)
gs[0] = -1
gs[N] = -1

ans = 1

rec(0, N)
print(ans)

Buggy python submission (verdict: Runtime Error):
mod = 10 ** 9 + 7

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

es = [[] for _ in range(N)]
g = [0] * N
for _ in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    es[a].append(b)
    g[a] += 1
    es[b].append(a)
    g[b] += 1

s = -1
b = -1
for i, gg in enumerate(g):
    if gg > b:
        b = gg
        s = i

gs = [0] * (N + 1)
gs[s] = -1
gs[N] = -1
visited = [False] * N
ans = 1


def rec(v, bf):
    global ans
    if visited[v]:
        return
    visited[v] = True
    gs[v] += 1
    gs[bf] += 1
    ans *= K - gs[bf]
    ans %= mod

    for nv in es[v]:
        if not visited[nv]:
            rec(nv, v)
    return


rec(s, N)
print(ans)

# print(gs)


Fixed submission:
import sys

sys.setrecursionlimit(10 ** 6)

mod = 10 ** 9 + 7

input = sys.stdin.readline


def rec(v, bf):
    global ans
    gs[v] += 1
    gs[bf] += 1
    ans = ans * (K - gs[bf]) % mod
    for nv in es[v]:
        if nv == bf: continue
        rec(nv, v)
    return


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

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

gs = [0] * (N + 1)
gs[0] = -1
gs[N] = -1

ans = 1

rec(0, N)
print(ans)