Problem p02985 (python)

Fixed submission:
import sys
sys.setrecursionlimit(10 ** 7)

MOD = 10**9 + 7
N, K = map(int,input().split())

edge = [[] for _ in range(N)]

for _ in range(N-1) :
    fromNode, toNode = map(int,input().split())

    fromNode -= 1
    toNode -= 1

    edge[fromNode].append(toNode)
    edge[toNode].append(fromNode)

# 深さ優先探索
def bfs(nowNode, fromNode) :
    colorNum = K  # 使用可能な色の数
    if fromNode == -1 :  # 根の場合
        colorNum -= 1
    else :
        colorNum -= 2

    if len(edge[nowNode]) - 1 > K :  # つながっている頂点数 - 1(親) == K までOK
        return 0

    caseNum = 1
    for nextNode in edge[nowNode] :
        if nextNode == fromNode :
            continue
        caseNum *= colorNum
        colorNum -= 1
        caseNum = caseNum % MOD

    for nextNode in edge[nowNode] :
        if nextNode == fromNode :
            continue
        caseNum *= bfs(nextNode, nowNode)
        caseNum = caseNum % MOD

    return caseNum

ans = bfs(0, - 1) * K
ans = ans % MOD
print(ans)

Buggy submission (verdict: Runtime Error):
from collections import deque

class Combination:
    def __init__(self, size, mod=10**9 + 7):
        self.size = size + 2
        self.mod = mod
        self.fact = [1, 1] + [0] * size
        self.factInv = [1, 1] + [0] * size
        self.inv = [0, 1] + [0] * size

        for i in range(2, self.size):
            self.fact[i] = self.fact[i - 1] * i % self.mod
            self.inv[i] = -self.inv[self.mod % i] * (self.mod // i) % self.mod
            self.factInv[i] = self.factInv[i - 1] * self.inv[i] % self.mod

    def npr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * self.factInv[n - r] % self.mod

    def ncr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * (self.factInv[r] * self.factInv[n - r] % self.mod) % self.mod

    def nhr(self, n, r):  # 重複組合せ
        return self.ncr(n + r - 1, n - 1)

    def factN(self, n):
        if n < 0:
            return 0
        return self.fact[n]

N, K = map(int, input().split())
comb = Combination(N + K)
MOD = 10**9 + 7

edges = [[] for _ in range(N)]
for _ in range(N - 1):
    fr, to = map(int, input().split())
    fr -= 1
    to -= 1
    edges[fr].append(to)
    edges[to].append(fr)

def dfs(now, pr):
    ret = 1

    cnt = 0
    for to in edges[now]:
        if to == pr:
            continue
        cnt += 1
        ret = (ret * dfs(to, now)) % MOD

    color = K - 1 if pr == -1 else K - 2
    ret = (ret * comb.npr(color, cnt)) % MOD

    return ret

print(dfs(0, -1) * K % MOD)

Buggy submission (verdict: Runtime Error):
from collections import deque

class Combination:
    def __init__(self, size, mod=10**9 + 7):
        self.size = size + 2
        self.mod = mod
        self.fact = [1, 1] + [0] * size
        self.factInv = [1, 1] + [0] * size
        self.inv = [0, 1] + [0] * size

        for i in range(2, self.size):
            self.fact[i] = self.fact[i - 1] * i % self.mod
            self.inv[i] = -self.inv[self.mod % i] * (self.mod // i) % self.mod
            self.factInv[i] = self.factInv[i - 1] * self.inv[i] % self.mod

    def npr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * self.factInv[n - r] % self.mod

    def ncr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * (self.factInv[r] * self.factInv[n - r] % self.mod) % self.mod

    def factN(self, n):
        if n < 0:
            return 0
        return self.fact[n]

N, K = map(int, input().split())
MOD = 10**9 + 7
edges = [[] for _ in range(N)]

for _ in range(N - 1):
    fr, to = map(int, input().split())
    fr -= 1
    to -= 1
    edges[fr].append(to)
    edges[to].append(fr)

comb = Combination(N + 100)

chCnt = [0] * N
que = deque([(0, -1)])
while que:
    now, pr = que.popleft()
    chCnt[now] = len(edges[now]) - 1
    for to in edges[now]:
        if to != pr:
            que.append((to, now))
chCnt[0] += 1

ans = K
que = deque([(0, -1)])
while que:
    now, pr = que.popleft()

    if pr == -1:
        ans *= comb.npr(K - 1, chCnt[now])
    else:
        ans *= comb.npr(K - 2, chCnt[now])

    ans %= MOD
    for to in edges[now]:
        if to != pr:
            que.append((to, now))

print(ans % MOD)

Buggy submission (verdict: Runtime Error):
MOD = 10**9 + 7
N, K = map(int,input().split())

edge = [[] for _ in range(N)]

for _ in range(N-1) :
    fromNode, toNode = map(int,input().split())

    fromNode -= 1
    toNode -= 1

    edge[fromNode].append(toNode)
    edge[toNode].append(fromNode)

# 深さ優先探索
def bfs(nowNode, fromNode) :
    colorNum = K  # 使用可能な色の数
    if fromNode == -1 :  # 根の場合
        colorNum -= 1
    else :
        colorNum -= 2

    if len(edge[nowNode]) - 1 > K :  # つながっている頂点数 - 1(親) == K までOK
        return 0

    caseNum = 1
    for nextNode in edge[nowNode] :
        if nextNode == fromNode :
            continue
        caseNum *= colorNum
        colorNum -= 1
        caseNum = caseNum % MOD

    for nextNode in edge[nowNode] :
        if nextNode == fromNode :
            continue
        caseNum *= bfs(nextNode, nowNode)
        caseNum = caseNum % MOD

    return caseNum

ans = bfs(0, - 1) * K
ans = ans % MOD
print(ans)

Buggy submission (verdict: Runtime Error):
MOD = 10**9 + 7
N, K = map(int,input().split())

edge = [[] for _ in range(N)]

for _ in range(N-1) :
    fromNode, toNode = map(int,input().split())

    fromNode -= 1
    toNode -= 1

    edge[fromNode].append(toNode)
    edge[toNode].append(fromNode)

# 深さ優先探索
def bfs(nowNode, fromNode) :
    colorNum = K  # 使用可能な色の数
    if fromNode == -1 :  # 根の場合
        colorNum -= 1
    else :
        colorNum -= 2

    if len(edge[nowNode]) > K :  # つながっている頂点数 - 1(親) == K までOK
        return 0

    caseNum = 1
    for nextNode in edge[nowNode] :
        if nextNode == fromNode :
            continue
        caseNum *= colorNum
        colorNum -= 1
        caseNum = caseNum % MOD

    for nextNode in edge[nowNode] :
        if nextNode == fromNode :
            continue
        caseNum *= bfs(nextNode, nowNode)
        caseNum = caseNum % MOD

    return caseNum

ans = bfs(0, - 1) * K
ans = ans % MOD
print(ans)