Problem p02985 (python)

Fixed submission:
import sys
sys.setrecursionlimit(100100)
from collections import deque
def factorials(M):#M!までのリストｘと其の逆元のリストyを返すmod INF
    INF=int(1e9+7)
    fac=[0]*(M+1)
    finv=[0]*(M+1)
    inv=[0]*(M+1)
    fac[0]=fac[1]=1
    finv[0]=finv[1]=1
    inv[1]=1
    for i in range(2,M+1):
        fac[i]=(fac[i-1]*i)%INF
        inv[i]=INF-(inv[INF%i]*(INF//i))%INF
        finv[i]=finv[i-1]*inv[i]%INF
    return fac,finv

N,K=map(int,input().split())
fac,finv=factorials(max(N,K))
def nCr(n,r):
    INF=int(1e9+7)
    if n<r or r<0 or n<0 :
        return 0
    return fac[n]*(finv[r]*finv[n-r]%INF)%INF
A=[0]*N
G=[[] for i in range(N)]
MOD=10**9+7
for i in range(N-1):
    a,b=map(int,input().split())
    a,b=a-1,b-1
    A[a]+=1
    A[b]+=1
    G[a].append(b)
    G[b].append(a)
ans=K
can=K
grand=0
gpare=-1
stack=deque([[0,gpare]])
while(stack):
    pare,gpare=stack.pop()
    childs=G[pare]
    ans*=nCr(K-1-grand,len(childs)-grand)*fac[len(childs)-grand]
    ans%=MOD
    grand=1
    for i in childs:
        if i==gpare:
            continue
        if A[i]-1==0:
            continue
        stack.append([i,pare])
print(ans)

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(100100)
from collections import deque
def factorials(M):#M!までのリストｘと其の逆元のリストyを返すmod INF
    INF=int(1e9+7)
    fac=[0]*(M+1)
    finv=[0]*(M+1)
    inv=[0]*(M+1)
    fac[0]=fac[1]=1
    finv[0]=finv[1]=1
    inv[1]=1
    for i in range(2,M+1):
        fac[i]=(fac[i-1]*i)%INF
        inv[i]=INF-(inv[INF%i]*(INF//i))%INF
        finv[i]=finv[i-1]*inv[i]%INF
    return fac,finv

N,K=map(int,input().split())
fac,finv=factorials(N)
def nCr(n,r):
    INF=int(1e9+7)
    if n<r or r<0 or n<0 :
        return 0
    return fac[n]*(finv[r]*finv[n-r]%INF)%INF
A=[0]*N
G=[[] for i in range(N)]
MOD=10**9+7
for i in range(N-1):
    a,b=map(int,input().split())
    a,b=a-1,b-1
    A[a]+=1
    A[b]+=1
    G[a].append(b)
    G[b].append(a)
ans=K
can=K
grand=0
gpare=-1
stack=deque([[0,gpare]])
while(stack):
    pare,gpare=stack.pop()
    childs=G[pare]
    ans*=nCr(K-1-grand,len(childs)-grand)*fac[len(childs)-grand]
    ans%=MOD
    grand=1
    for i in childs:
        if i==gpare:
            continue
        if A[i]-1==0:
            continue
        stack.append([i,pare])
print(ans)

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(100100)
from collections import deque
def factorials(M):#M!までのリストｘと其の逆元のリストyを返すmod INF
    INF=int(1e9+7)
    fac=[0]*(M+1)
    finv=[0]*(M+1)
    inv=[0]*(M+1)
    fac[0]=fac[1]=1
    finv[0]=finv[1]=1
    inv[1]=1
    for i in range(2,M+1):
        fac[i]=(fac[i-1]*i)%INF
        inv[i]=INF-(inv[INF%i]*(INF//i))%INF
        finv[i]=finv[i-1]*inv[i]%INF
    return fac,finv

N,K=map(int,input().split())
fac,finv=factorials(K)
def nCr(n,r):
    INF=int(1e9+7)
    if n<r or r<0 or n<0 :
        return 0
    return fac[n]*(finv[r]*finv[n-r]%INF)%INF
A=[0]*N
G=[[] for i in range(N)]
MOD=10**9+7
for i in range(N-1):
    a,b=map(int,input().split())
    a,b=a-1,b-1
    A[a]+=1
    A[b]+=1
    G[a].append(b)
    G[b].append(a)
ans=K
can=K
grand=0
gpare=-1
stack=deque([[0,gpare]])
while(stack):
    pare,gpare=stack.pop()
    childs=G[pare]
    ans*=nCr(K-1-grand,len(childs)-grand)*fac[len(childs)-grand]
    ans%=MOD
    grand=1
    for i in childs:
        if i==gpare:
            continue
        if A[i]-1==0:
            continue
        stack.append([i,pare])
print(ans)

Buggy submission (verdict: Runtime Error):
from collections import deque
def factorials(M):#M!までのリストｘと其の逆元のリストyを返すmod INF
    INF=int(1e9+7)
    fac=[0]*(M+1)
    finv=[0]*(M+1)
    inv=[0]*(M+1)
    fac[0]=fac[1]=1
    finv[0]=finv[1]=1
    inv[1]=1
    for i in range(2,M+1):
        fac[i]=(fac[i-1]*i)%INF
        inv[i]=INF-(inv[INF%i]*(INF//i))%INF
        finv[i]=finv[i-1]*inv[i]%INF
    return fac,finv

N,K=map(int,input().split())
fac,finv=factorials(K)
def nCr(n,r):
    INF=int(1e9+7)
    if n<r or r<0 or n<0 :
        return 0
    return fac[n]*(finv[r]*finv[n-r]%INF)%INF
A=[0]*N
G=[[] for i in range(N)]
MOD=10**9+7
for i in range(N-1):
    a,b=map(int,input().split())
    a,b=a-1,b-1
    A[a]+=1
    A[b]+=1
    G[a].append(b)
    G[b].append(a)
ans=K
can=K
grand=0
gpare=-1
stack=deque([[0,gpare]])
while(stack):
    pare,gpare=stack.pop()
    childs=G[pare]
    ans*=nCr(K-1-grand,len(childs)-grand)*fac[len(childs)-grand]
    ans%=MOD
    grand=1
    for i in childs:
        if i==gpare:
            continue
        if A[i]-1==0:
            continue
        stack.append([i,pare])
print(ans)