Problem p02985 (python)

Fixed submission:
# -*- coding: utf-8 -*-
"""
Created on Tue Aug 25 08:44:21 2020

@author: teppe
"""

from collections import deque

def prepare(n, MOD):
 
    # 1! - n! の計算
    f = 1
    factorials = [1]  # 0!の分
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    # n!^-1 の計算
    inv = pow(f, MOD - 2, MOD)
    # n!^-1 - 1!^-1 の計算
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
     
    return factorials, invs

MOD = 10**9+7
fact, fact_inv = prepare(10+10**5, MOD)

def perm(n,k):
  if k > n or k < 0:
    return 0
  return fact[n] * fact_inv[n-k] % MOD


n, k = map(int,input().split())
e = [[] for i in range(n)]
for i in range(n-1):
    a, b = map(int,input().split())
    a -= 1
    b -= 1
    e[a].append(b)
    e[b].append(a)
 
colored = [False]*n
colored[0] = True
num = len(e[0])
ans = perm(k, 1+num)
d = deque()
for i in e[0]:
    colored[i] = True
    d.append(i)
while d:
    f = d.pop()
    num = len(e[f]) - 1
    if num == 0:
        continue
    ans *= perm(k-2, num)
    ans %= MOD
    for i in e[f]:
        if not colored[i]:
            colored[i] = True
            d.appendleft(i)
print(ans % MOD)

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

def prepare(n, MOD):
 
    # 1! - n! の計算
    f = 1
    factorials = [1]  # 0!の分
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    # n!^-1 の計算
    inv = pow(f, MOD - 2, MOD)
    # n!^-1 - 1!^-1 の計算
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
     
    return factorials, invs


MOD = 10**9+7
fact, fact_inv = prepare(10+10**5, MOD)


n, k = map(int,input().split())
e = [[] for i in range(n)]
for i in range(n-1):
    a, b = map(int,input().split())
    a -= 1
    b -= 1
    e[a].append(b)
    e[b].append(a)
    
colored = [False]*n
# 根を決める
for i in range(n):
    if len(e[i]) == 1:
        s = i
colored = [False]*n
# 根を決める
for i in range(n):
    if len(e[i]) == 1:
        s = i
colored[s] = True
num = len(e[s])
ans = fact[k] * fact_inv[k-1-num] % MOD
ans %= MOD
d = deque()
for i in e[0]:
    colored[i] = True
    d.append(i)
while d:
    f = d.pop()
    num = len(e[f]) - 1
    if num == 0:
        continue
    ans *= fact[k-2] * fact_inv[k-2-num] % MOD
    ans %= MOD
    for i in e[f]:
        if not colored[i]:
            colored[i] = True
            d.appendleft(i)
print(ans % MOD)

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

def prepare(n, MOD):
 
    # 1! - n! の計算
    f = 1
    factorials = [1]  # 0!の分
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    # n!^-1 の計算
    inv = pow(f, MOD - 2, MOD)
    # n!^-1 - 1!^-1 の計算
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
     
    return factorials, invs


MOD = 10**9+7
fact, fact_inv = prepare(10+10**5, MOD)


n, k = map(int,input().split())
e = [[] for i in range(n)]
for i in range(n-1):
    a, b = map(int,input().split())
    a -= 1
    b -= 1
    e[a].append(b)
    e[b].append(a)
    
colored = [False]*n
# 根を決める
for i in range(n):
    if len(e[i]) == 1:
        s = i
colored[s] = True
ans = k
num = len(e[s])
ans *= fact[k-1] * fact_inv[k-1-num] % MOD
ans %= MOD
d = deque()
for i in e[0]:
    colored[i] = True
    d.append(i)
while d:
    f = d.pop()
    num = len(e[f]) - 1
    if num == 0:
        continue
    ans *= fact[k-2] * fact_inv[k-2-num] % MOD
    ans %= MOD
    for i in e[f]:
        if not colored[i]:
            colored[i] = True
            d.append(i)
print(ans % MOD)

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

def prepare(n, MOD):
 
    # 1! - n! の計算
    f = 1
    factorials = [1]  # 0!の分
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    # n!^-1 の計算
    inv = pow(f, MOD - 2, MOD)
    # n!^-1 - 1!^-1 の計算
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
     
    return factorials, invs


MOD = 10**9+7
fact, fact_inv = prepare(10+10**5, MOD)


n, k = map(int,input().split())
e = [[] for i in range(n)]
for i in range(n-1):
    a, b = map(int,input().split())
    a -= 1
    b -= 1
    e[a].append(b)
    e[b].append(a)
    
colored = [False]*n
# 根を決める
for i in range(n):
    if len(e[i]) == 1:
        s = i
colored[s] = True
ans = k
num = len(e[s])
ans *= fact[k-1] * fact_inv[k-1-num] % MOD
ans %= MOD
d = deque()
for i in e[0]:
    colored[i] = True
    d.append(i)
while d:
    f = d.pop()
    num = len(e[f]) - 1
    if num == 0:
        continue
    ans *= fact[k-2] * fact_inv[k-2-num] % MOD
    ans %= MOD
    for i in e[f]:
        if not colored[i]:
            colored[i] = True
            d.appendleft(i)
print(ans % MOD)

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

MOD = 10**9+7
n, k = map(int,input().split())
e = [[] for i in range(n)]
for i in range(n-1):
    a, b = map(int,input().split())
    a -= 1
    b -= 1
    e[a].append(b)
    e[b].append(a)
    
color = [-1]*n
d = deque()
d.append(0)
while d:
    f = d.pop()
    tmp = deque()
    tmp.append([f, 0])
    p = deque()
    while True:
        cf, cd = tmp.pop()
        if cd >= 2:
          break
        for i in e[cf]:
            if i == f:
                continue
            tmp.appendleft([i, cd+1])
            if not i in p:
                p.append(i)
    cnt = 0
    while p:
        cf = p.pop()
        if color[cf] != -1:
            cnt += 1
    color[f] = k - cnt
    for i in e[f]:
        if color[i] == -1:
            d.appendleft(i)
            
ans = 1
for i in range(n):
    ans = ans * color[i] % MOD
print(ans)