Problem p02985 (python)

Fixed submission:
from collections import deque

modulo = 10 ** 9 + 7

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

def P(n, k):
    if n < k:
        return 0
    f = 1
    for i in range(n, n - k, -1):
        f = f * i % modulo
    return f

visited = set()
q = deque([1])
ncoloring = K  # num of coloring of the root

while len(q) > 0:
    u = q.popleft()
    visited.add(u)

    # coloring of the children
    children = [c for c in adj[u] if c not in visited]
    ncoloring *= P(K - 1 if u == 1 else K - 2, len(children))
    ncoloring %= modulo

    q.extend([c for c in children])

print(ncoloring)

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

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

def P(n, k):
    if n < k:
        return 0
    f = 1
    for i in range(n, n - k, -1):
        f = f * i % modulo
    return f

visited = set()

def ncoloring(root, d):
    """the number of coloring of a subtree at depth d
       when the color of the root has been decided."""
    visited.add(root)
    children = [s for s in adj[root] if s not in visited]
    remainingcolors = K - 2 if d > 0 else K - 1

    # coloring of the children
    p = P(remainingcolors, len(children)) % modulo

    # coloring of the subtrees
    for c in children:
        p = p * ncoloring(c, d + 1) % modulo
    return p

print(ncoloring(1, 0) * K % modulo)

Buggy submission (verdict: Runtime Error):
from math import factorial

modulo = 10 ** 9 + 7

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

def P(n, k):
    return factorial(n) // factorial(n - k) if n >= k else 0

visited = set()

def ncoloring(root, d):
    """the number of coloring of a subtree at depth d
       when the color of the root has been decided."""
    visited.add(root)
    children = [s for s in adj[root] if s not in visited]
    remainingcolors = K - 2 if d > 0 else K - 1

    # coloring of the children
    p = P(remainingcolors, len(children)) % modulo

    # coloring of the subtrees
    for c in children:
        p = p * ncoloring(c, d + 1) % modulo
    return p

print(ncoloring(1, 0) * K % modulo)

Buggy submission (verdict: Runtime Error):
from math import factorial

modulo = 10 ** 9 + 7

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

def P(n, k):
    return factorial(n) // factorial(n - k) if n >= k else 0

visited = set()

def ncoloring(root, d):
    """the number of coloring of a subtree at depth d
       when the color of the root has been decided."""
    visited.add(root)
    children = [s for s in adj[root] if s not in visited]
    remainingcolors = K - 2 if d > 0 else K - 1

    # coloring of the children
    p = P(remainingcolors, len(children)) % modulo

    # coloring of the subtrees
    for c in children:
        p = p * ncoloring(c, d + 1) % modulo
    return p

print(ncoloring(1, 0) * K % modulo)