Problem p02985 (python)

Fixed submission:
import sys
import math
sys.setrecursionlimit(1000000)
mod=1000000007
class Node:
    def __init__(self):
        self.next=[]
    def get_data(self,new_next,weight=1):
        self.next.append(new_next)
def BFS(i,depth,K):  
    depth+=1
    tmp=i
    seki=1
    num=len(tmp)
    if depth==1:
        calc=K-1
        loop=range(calc,calc-num,-1)
        for i in loop:
            seki*=i%1000000007

        
    else:
        calc=K-2
        num-=1
        if calc>=num:
            seki=cache[num]
        else:
            print(0)
            exit()

            
            
    for each in tmp:
        if not check_node[each]:
            check_node[each]=True
            seki*=BFS(node[each].next,depth,K)%mod
    return seki


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

if K>2:
    cache=[0 for i in range(K-2)]
    cache[0]=1
    for i in range(1,K-2):
        cache[i]=cache[i-1]*(K-1-i)%mod
    cache.append(cache[-1])
else:
    cache=[1,1]
node=[Node() for _ in range(N)]
check_node=[False for _ in range(N)]
check_node[0]=True
for i in range(N-1):
    p,n=list(map(int,input().split()))
    node[n-1].get_data(p-1)
    node[p-1].get_data(n-1)
start=0
d=0

com=K*BFS(node[0].next,d,K)
print(int(com)%mod)

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(1000000)
mod=1000000007

class Node:
    def __init__(self):
        self.next=[]
    def get_data(self,new_next,weight=1):
        self.next.append(new_next)
def BFS(i,depth,K):  
    depth+=1
    tmp=i
    seki=1
    num=len(tmp)
    if depth==1:
        calc=K-1
        loop=range(calc,calc-num,-1)
        for i in loop:
            seki*=i%1000000007

        
    else:
        calc=K-2
        num-=1
        if calc>=num:
            seki=cache[num]
        else:
            print(0)
            exit()

            
            
    for each in tmp:
        if not check_node[each]:
            check_node[each]=True
            seki*=BFS(node[each].next,depth,K)%mod
    return seki


N,K=list(map(int,input().split()))
cache=[0 for i in range(K-2)]
cache[0]=1
for i in range(1,K-2):
    cache[i]=cache[i-1]*(K-1-i)%mod
cache.append(cache[-1])
node=[Node() for _ in range(N)]
check_node=[False for _ in range(N)]
check_node[0]=True
for i in range(N-1):
    p,n=list(map(int,input().split()))
    node[n-1].get_data(p-1)
    node[p-1].get_data(n-1)
start=0
d=0

com=K*BFS(node[0].next,d,K)
print(int(com)%mod)

Buggy submission (verdict: Runtime Error):
import sys
import math
sys.setrecursionlimit(1000000)
mod=1000000007
def power_func(a,b,p):
    """a^b mod p を求める"""
    if b==0: 
        return 1
    if b%2==0:
        d=power_func(a,b//2,p)
        return d*d %p
    if b%2==1:
        return (a*power_func(a,b-1,p ))%p
class Node:
    def __init__(self):
        self.next=[]
    def get_data(self,new_next,weight=1):
        self.next.append(new_next)
def BFS(i,depth,K):  
    depth+=1
    tmp=i
    seki=1
    num=len(tmp)
    if depth==1:
        calc=K-1

        
    else:
        calc=K-2
        num-=1
    """
    loop=range(calc,calc-(num-diff),-1)
    for i in loop:
        seki*=i%1000000007
    """
    seki=(math.factorial(calc)//math.factorial(calc-num))%mod
    #"""
    #if calc-num>=0:
        #fac=math.factorial(calc-(num-diff))%mod
        #seki*=((math.factorial(calc)%mod)*power_func(fac,mod-2,mod))%mod
        #seki=(math.factorial(calc)//math.factorial(calc-num))%mod
    #else:
    #    return 0
    #"""
            
    for each in tmp:
        if not check_node[each]:
            check_node[each]=True
            seki*=BFS(node[each].next,depth,K)%mod
    return seki


N,K=list(map(int,input().split()))
node=[Node() for _ in range(N)]
check_node=[False for _ in range(N)]
check_node[0]=True
for i in range(N-1):
    p,n=list(map(int,input().split()))
    node[n-1].get_data(p-1)
    node[p-1].get_data(n-1)
start=0
d=0

com=K*BFS(node[0].next,d,K)
print(int(com)%mod)

Buggy submission (verdict: Runtime Error):
import sys
import math
sys.setrecursionlimit(1000000)
mod=1000000007
def power_func(a,b,p):
    """a^b mod p を求める"""
    if b==0: 
        return 1
    if b%2==0:
        d=power_func(a,b//2,p)
        return d*d %p
    if b%2==1:
        return (a*power_func(a,b-1,p ))%p
class Node:
    def __init__(self):
        self.next=[]
    def get_data(self,new_next,weight=1):
        self.next.append(new_next)
def BFS(i,depth,K):  
    depth+=1
    tmp=i
    seki=1
    num=len(tmp)
    if depth==1:
        calc=K-1
        diff=0

        
    else:
        calc=K-2
        diff=1
    #for i in range(calc,calc-(num-diff),-1):
    #    seki*=i%1000000007
    if num-diff>0 and num-diff<calc:
        fac=math.factorial(calc-(num-diff))%mod
        seki*=((math.factorial(calc)%mod)*power_func(fac,mod-2,mod))%mod
    elif num-diff>calc
        seki=0
            
    for each in tmp:
        if not check_node[each]:
            check_node[each]=True
            seki*=BFS(node[each].next,depth,K)%mod
    return seki


N,K=list(map(int,input().split()))
node=[Node() for _ in range(N)]
check_node=[False for _ in range(N)]
check_node[0]=True
for i in range(N-1):
    p,n=list(map(int,input().split()))
    node[n-1].get_data(p-1)
    node[p-1].get_data(n-1)
start=0
d=0

com=K*BFS(node[0].next,d,K)
print(int(com)%mod)

Buggy submission (verdict: Runtime Error):
import sys
import math
sys.setrecursionlimit(1000000)
mod=1000000007
def power_func(a,b,p):
    """a^b mod p を求める"""
    if b==0: 
        return 1
    if b%2==0:
        d=power_func(a,b//2,p)
        return d*d %p
    if b%2==1:
        return (a*power_func(a,b-1,p ))%p
class Node:
    def __init__(self):
        self.next=[]
    def get_data(self,new_next,weight=1):
        self.next.append(new_next)
def BFS(i,depth,K):  
    depth+=1
    tmp=i
    seki=1
    num=len(tmp)
    if depth==1:
        calc=K-1
        diff=0

        
    else:
        calc=K-2
        diff=1
    #for i in range(calc,calc-(num-diff),-1):
    #    seki*=i%1000000007
    if num-diff>0:
        fac=math.factorial(calc-(num-diff))%mod
        seki*=((math.factorial(calc)%mod)*power_func(fac,mod-2,mod))%mod
            
    for each in tmp:
        if not check_node[each]:
            check_node[each]=True
            seki*=BFS(node[each].next,depth,K)%mod
    return seki


N,K=list(map(int,input().split()))
node=[Node() for _ in range(N)]
check_node=[False for _ in range(N)]
check_node[0]=True
for i in range(N-1):
    p,n=list(map(int,input().split()))
    node[n-1].get_data(p-1)
    node[p-1].get_data(n-1)
start=0
d=0

com=K*BFS(node[0].next,d,K)
print(int(com)%mod)

Buggy submission (verdict: Runtime Error):
import sys
import math
sys.setrecursionlimit(1000000)
class Node:
    def __init__(self):
        self.next=[]
    def get_data(self,new_next,weight=1):
        self.next.append(new_next)
def BFS(i,depth,K):  
    depth+=1
    tmp=i
    seki=1
    num=len(tmp)
    if depth==1:
        calc=K-1
        diff=0
        #for i in range(calc,max(1,calc-(len(tmp)-diff)),-1):
        #seki*=special.perm(calc,num-diff)
        #for i in range(calc,calc-(num-diff),-1):
        #    seki*=i%1000000007
        
    else:
        calc=K-2
        diff=1
        #for i in range(calc,calc-(num-diff),-1):
        #    seki*=i%1000000007
    seki*=math.factorial(calc)/math.factorial(calc-(num-diff))
            
    for each in tmp:
        if not check_node[each]:
            check_node[each]=True
            seki*=BFS(node[each].next,depth,K)%1000000007
    return seki


N,K=list(map(int,input().split()))
node=[Node() for _ in range(N)]
check_node=[False for _ in range(N)]
check_node[0]=True
for i in range(N-1):
    p,n=list(map(int,input().split()))
    node[n-1].get_data(p-1)
    node[p-1].get_data(n-1)
start=0
d=0

com=K*BFS(node[0].next,d,K)
print(int(com)%1000000007)

Buggy submission (verdict: Runtime Error):
import sys
from scipy import special
sys.setrecursionlimit(1000000)
class Node:
    def __init__(self):
        self.next=[]
    def get_data(self,new_next,weight=1):
        self.next.append(new_next)
def BFS(i,depth,K):  
    depth+=1
    tmp=i
    seki=1
    num=len(tmp)
    if depth==1:
        calc=K-1
        diff=0
        #for i in range(calc,max(1,calc-(len(tmp)-diff)),-1):
        seki*=special.perm(calc,num-diff)
        #for i in range(calc,calc-(num-diff),-1):
        #    seki*=i%1000000007
        
    else:
        calc=K-2
        diff=1
        #for i in range(calc,calc-(num-diff),-1):
        #    seki*=i%1000000007
    seki*=special.perm(calc,num-diff)
            
    for each in tmp:
        if not check_node[each]:
            check_node[each]=True
            seki*=BFS(node[each].next,depth,K)%1000000007
    return seki


N,K=list(map(int,input().split()))
node=[Node() for _ in range(N)]
check_node=[False for _ in range(N)]
check_node[0]=True
for i in range(N-1):
    p,n=list(map(int,input().split()))
    node[n-1].get_data(p-1)
    node[p-1].get_data(n-1)
start=0
d=0

com=K*BFS(node[0].next,d,K)
print(int(com)%1000000007)

Buggy submission (verdict: Runtime Error):
class Node:
    def __init__(self):
        self.next=[]
    def get_data(self,new_next,weight=1):
        self.next.append({new_next:weight})
def BFS(i,depth,K):  
    depth+=1
    tmp=[list(j.keys())[0] for j in i]


    if depth==1:
        calc=K-1
        diff=0
    else:
        calc=K-2
        diff=1
    seki=1
    if (len(tmp))>1 or depth<2:
        for i in range(calc,max(1,calc-(len(tmp)-diff)),-1):
            seki*=i
            
    for each in tmp:
        if not check_node[each]:
            check_node[each]=True
            
            seki*=BFS(node[each].next,depth,K)
    return seki


N,K=list(map(int,input().split()))
node=[Node() for _ in range(N)]
check_node=[False for _ in range(N)]
check_node[0]=True
for i in range(N-1):
    p,n=list(map(int,input().split()))
    node[n-1].get_data(p-1)
    node[p-1].get_data(n-1)
start=0
d=0

com=K*BFS(node[0].next,d,K)
print(com%1000000007)

Buggy submission (verdict: Runtime Error):
class Node:
    def __init__(self):
        self.next=[]
    def get_data(self,new_next,weight=1):
        self.next.append({new_next:weight})
def BFS(i,depth,K):  
    depth+=1
    tmp=[list(j.keys())[0] for j in i]
    if depth==0:
        seki=K
    else:
        if depth==1:
            calc=K-1
            diff=0
        else:
            calc=K-2
            diff=1
        seki=1
        if (len(tmp))>1 or depth<2:
            for i in range(calc,max(1,calc-(len(tmp)-diff)),-1):
                seki*=i
            
    for each in tmp:
        if not check_node[each]:
            check_node[each]=True
            
            seki*=BFS(node[each].next,depth,K)
    return seki


N,K=list(map(int,input().split()))
node=[Node() for _ in range(N)]
check_node=[False for _ in range(N)]
check_node[0]=True
for i in range(N-1):
    p,n=list(map(int,input().split()))
    node[n-1].get_data(p-1)
    node[p-1].get_data(n-1)
start=0
d=0

com=K*BFS(node[0].next,d,K)
print(com%1000000007)