Buggy python submission (verdict: Time Limit Exceeded):
import operator as op
from functools import reduce
 
def npr(n, r):
    numer = reduce(op.mul, range(n, n-r, -1), 1)
    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

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

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

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

Buggy python submission (verdict: Time Limit Exceeded):
import operator as op
from functools import reduce
 
def npr(n, r):
    numer = reduce(op.mul, range(n, n-r, -1), 1)
    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
child_num = [child_num[0]] + [child_num[i] - 1 for i in range(1, N)]


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

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

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

Buggy python submission (verdict: Time Limit Exceeded):
import operator as op
from functools import reduce
 
def npr(n, r):
    numer = reduce(op.mul, range(n, n-r, -1), 1)
    return numer


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

# edge_mat[i][j] = 1 iff vertex_i and vertex_j are connected
edge_mat = [[0 for j in range(N)] for i in range(N)]
for k in range(N - 1):
    a, b = list(map(int, input().split()))
    a -= 1
    b -= 1
    edge_mat[a][b] = 1
    edge_mat[b][a] = 1

# ナンバリングは０オリジン
# 頂点０をrootとする

# depth1 = 階層１の頂点を列挙
num = 0
for j in range(1, N):
    if edge_mat[0][j] == 1:
        num += 1

# 各頂点から出る子の個数を列挙
child_num = [0 for i in range(N)]
child_num[0] = num
for j in range(1, N):
    child_num[j] = sum(edge_mat[j]) - 1

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

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

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

Buggy python submission (verdict: Time Limit Exceeded):
import operator as op
from functools import reduce
 
def npr(n, r):
    numer = reduce(op.mul, range(n, n-r, -1), 1)
    return numer


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

# edge_mat[i][j] = 1 iff vertex_i and vertex_j are connected
edge_mat = [[0 for j in range(N)] for i in range(N)]
for k in range(N - 1):
    a, b = list(map(int, input().split()))
    a -= 1
    b -= 1
    edge_mat[a][b] = 1
    edge_mat[b][a] = 1

# ナンバリングは０オリジン
# 頂点０をrootとする

# depth1 = 階層１の頂点を列挙
depth1 = []
for j in range(1, N):
    if edge_mat[0][j] == 1:
        depth1.append(j)

# 各頂点から出る子の個数を列挙
child_num = [0 for i in range(N)]
child_num[0] = len(depth1)
for j in range(1, N):
    child_num[j] = sum(edge_mat[j]) - 1

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

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

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