Problem p02985 (python)

Fixed submission:
from collections import deque
import math
import sys
mod = 10**9+7
N,K = map(int,input().split())

#k
Kperm =[1,K]
pre = K
for i in range(2,K+1):
    pre = (pre*(K+1-i))%mod
    Kperm.append(pre)


#K-2Pxの計算のメモ化
K_2perm =[1,K-2]
pres = K-2
for i in range(2,K-1):
    pres = (pres*(K-1-i))%mod
    K_2perm.append(pres)

child = [[] for i in range(N)]
for hoge in range(N-1):
    a,b = [int(i)-1 for i in input().split()]#点を0-indexedになおす
    child[a].append(b)
    child[b].append(a)

if len(child[0])>=K:
    print(0);sys.exit()
ans = Kperm[len(child[0])+1]
#DFSしながら塗る
went = [False] * N
queue = deque()
queue.append(0)
went[0] = True
while queue:
    cur = queue.pop()
    if cur!=0 and len(child[cur])>=K:
        print(0)
        sys.exit()
    if cur!=0:
        ans *= K_2perm[len(child[cur])-1]
        ans %= mod
    for togo in child[cur]:
        if not went[togo]:
            went[togo] = True
            queue.append(togo)
print(ans)

Buggy submission (verdict: Runtime Error):
from collections import deque
import math
mod = 10**9+7
N,K = map(int,input().split())


Kperm =[1,K]
pre = K
for i in range(2,K+1):
    pre = (pre*(K+1-i))%mod
    Kperm.append(pre)


#K-2Pxの計算のメモ化
K_2perm =[1,K-2]
pres = K-2
for i in range(2,K-1):
    pres = (pres*(K-1-i))%mod
    K_2perm.append(pres)

child = [[] for i in range(N)]
for hoge in range(N-1):
    a,b = [int(i)-1 for i in input().split()]#点を0-indexedになおす
    child[a].append(b)
    child[b].append(a)


ans = Kperm[len(child[0])+1]
#DFSしながら塗る
went = [False] * N
queue = deque()
queue.append(0)
went[0] = True
while queue:
    cur = queue.popleft()
    if cur!=0:
        ans *= K_2perm[len(child[cur])-1]
        ans %= mod
    for togo in child[cur]:
        if not went[togo]:
            went[togo] = True
            queue.append(togo)
print(ans)

Buggy submission (verdict: Runtime Error):
from collections import deque
import math
mod = 10**9+7
N,K = map(int,input().split())


Kperm =[1,K]
pre = K
for i in range(2,K+1):
    pre = (pre*(K+1-i))%mod
    Kperm.append(pre)


#K-2Pxの計算のメモ化
K_2perm =[1,K-2]
pres = K-2
for i in range(2,K-1):
    pres = (pres*(K-1-i))%mod
    K_2perm.append(pres)

child = [[] for i in range(N)]
for hoge in range(N-1):
    a,b = [int(i)-1 for i in input().split()]#点を0-indexedになおす
    child[a].append(b)
    child[b].append(a)


ans = Kperm[len(child[0])+1]
#DFSしながら塗る
went = [False] * N
queue = deque()
queue.append(0)
went[0] = True
while queue:
    cur = queue.pop()
    if cur!=0:
        ans *= K_2perm[len(child[cur])-1]
        ans %= mod
    for togo in child[cur]:
        if not went[togo]:
            went[togo] = True
            queue.append(togo)
print(ans)

Buggy submission (verdict: Runtime Error):
from collections import deque
import math
mod = 10**9+7
N,K = map(int,input().split())

def fact(x):
    a = 1
    for i in range(x):
        a *= i+1
        a = a%mod
    return a

#KPxの計算用。一回だけ使う
def Perm(n,r):#aPb
    return fact(n) // fact(n - r)

#K-2Pxの計算のメモ化
K_2perm =[1,K-2]
pres = K-2
for i in range(2,K-1):
    pres = (pres*(K-1-i))%mod
    K_2perm.append(pres)

child = [[] for i in range(N)]
for hoge in range(N-1):
    a,b = [int(i)-1 for i in input().split()]#点を0-indexedになおす
    child[a].append(b)
    child[b].append(a)


ans = Perm(K,len(child[0])+1)%mod
#DFSしながら塗る
went = [False] * N
queue = deque()
queue.append(0)
went[0] = True
while queue:
    cur = queue.pop()
    if cur!=0:
        ans *= K_2perm[len(child[cur])-1]
        ans %= mod
    for togo in child[cur]:
        if not went[togo]:
            went[togo] = True
            queue.append(togo)
print(ans)

Buggy submission (verdict: Runtime Error):
from collections import deque
import math
mod = 10**9+7
N,K = map(int,input().split())

#KPxの計算用。一回だけ使う
def Perm(n,r):#aPb
    return math.factorial(n) // math.factorial(n - r)

#K-2Pxの計算のメモ化
K_2perm =[1,K-2]
pres = K-2
for i in range(2,K-1):
    pres = (pres*(K-1-i))%mod
    K_2perm.append(pres)

child = [[] for i in range(N)]
for hoge in range(N-1):
    a,b = [int(i)-1 for i in input().split()]#点を0-indexedになおす
    child[a].append(b)
    child[b].append(a)


ans = Perm(K,len(child[0])+1)%mod
#DFSしながら塗る
went = [False] * N
queue = deque()
queue.append(0)
went[0] = True
while queue:
    cur = queue.pop()
    if cur!=0:
        ans *= K_2perm[len(child[cur])-1]
        ans %= mod
    for togo in child[cur]:
        if not went[togo]:
            went[togo] = True
            queue.append(togo)
print(ans)

Buggy submission (verdict: Runtime Error):
from collections import deque
import math
mod = 10**9+7
N,K = map(int,input().split())

def facto(x):
    r = 1
    for i in range(1,x+1):
        r *= i
        r %= mod
    return r

def Perm(n,r):#aPb
    return facto(n) // facto(n - r)

K_2perm =[1,K-2]
pres = K-2
#K_2perm[i] = K-2Pi
for i in range(2,K-1):
    pres = (pres*(K-1-i))%mod
    K_2perm.append(pres)
child = [[] for i in range(N)]
for hoge in range(N-1):
    a,b = [int(i)-1 for i in input().split()]
    child[a].append(b)
    child[b].append(a)


went = [False] * N
queue = deque()
queue.append(0)
went[0] = True

ans = Perm(K,len(child[0])+1)%mod
while queue:
    cur = queue.pop()
    if cur!=0:
        ans *= K_2perm[len(child[cur])-1]
        ans %= mod
    for togo in child[cur]:
        if not went[togo]:
            went[togo] = True
            queue.append(togo)
print(ans)

Buggy submission (verdict: Runtime Error):
from collections import deque
import math
mod = 10**9+7
N,K = map(int,input().split())

def facto(x):
    r = 0
    for i in range(1,x+1):
        r *= i
        r %= mod
    return r

def Perm(n,r):#aPb
    return facto(n) // facto(n - r)

K_2perm =[1,K-2]
pres = K-2
#K_2perm[i] = K-2Pi
for i in range(2,K-1):
    pres = (pres*(K-1-i))%mod
    K_2perm.append(pres)
child = [[] for i in range(N)]
for hoge in range(N-1):
    a,b = [int(i)-1 for i in input().split()]
    child[a].append(b)
    child[b].append(a)
went = [False] * N
queue = deque()
queue.append(0)
went[0] = True

ans = Perm(K,len(child[0])+1)%mod
while queue:
    cur = queue.pop()
    if cur!=0:
        ans *= K_2perm[len(child[cur])-1]
        ans %= mod
    for togo in child[cur]:
        if not went[togo]:
            went[togo] = True
            queue.append(togo)
print(ans)

Buggy submission (verdict: Runtime Error):
from collections import deque
import math
mod = 10**9+7
N,K = map(int,input().split())

def Perm(n,r):#aPb
    return math.factorial(n) // math.factorial(n - r)

K_2perm =[1,K-2]
pres = K-2
#K_2perm[i] = K-2Pi
for i in range(2,K-1):
    pres = (pres*(K-1-i))%mod
    K_2perm.append(pres)
child = [[] for i in range(N)]
for hoge in range(N-1):
    a,b = [int(i)-1 for i in input().split()]
    child[a].append(b)
    child[b].append(a)
went = [False] * N
queue = deque()
queue.append(0)
went[0] = True

x = len(child[0]) + 1
ans = (K_2perm[x] *(K-1)*K//(K-1-x)//(K-x) )%mod
while queue:
    cur = queue.pop()
    if cur!=0:
        ans *= K_2perm[len(child[cur])-1]
        ans %= mod
    for togo in child[cur]:
        if not went[togo]:
            went[togo] = True
            queue.append(togo)
print(ans)

Buggy submission (verdict: Runtime Error):
from collections import deque
import math
mod = 10**9+7
N,K = map(int,input().split())

#KPxの計算用。一回だけ使う
def Perm(n,r):#aPb
    return math.factorial(n) // math.factorial(n - r)

#K-2Pxの計算のメモ化
K_2perm =[1,K-2]
pres = K-2
for i in range(2,K-1):
    pres = (pres*(K-1-i))%mod
    K_2perm.append(pres)

child = [[] for i in range(N)]
for hoge in range(N-1):
    a,b = [int(i)-1 for i in input().split()]#点を0-indexedになおす
    child[a].append(b)
    child[b].append(a)

x = len(child[0]) + 1
ans = (K_2perm[x] *(K-1)*K//(K-1-x)//(K-x) )%mod
#DFSしながら塗る
went = [False] * N
queue = deque()
queue.append(0)
went[0] = True
while queue:
    cur = queue.pop()
    if cur!=0:
        ans *= K_2perm[len(child[cur])-1]
        ans %= mod
    for togo in child[cur]:
        if not went[togo]:
            went[togo] = True
            queue.append(togo)
print(ans)

Buggy submission (verdict: Runtime Error):
from collections import deque
import math
mod = 10**9+7
N,K = map(int,input().split())

#KPxの計算用。一回だけ使う
def Perm(n,r):#aPb
    return math.factorial(n) // math.factorial(n - r)

#K-2Pxの計算のメモ化
K_2perm =[1,K-2]
pres = K-2
for i in range(2,K-1):
    pres = (pres*(K-1-i))%mod
    K_2perm.append(pres)

child = [[] for i in range(N)]
for hoge in range(N-1):
    a,b = [int(i)-1 for i in input().split()]#点を0-indexedになおす
    child[a].append(b)
    child[b].append(a)


ans = Perm(K,len(child[0])+1)%mod
#DFSしながら塗る
went = [False] * N
queue = deque()
queue.append(0)
went[0] = True
while queue:
    cur = queue.pop()
    if cur!=0:
        ans *= K_2perm[len(child[cur])-1]
        ans %= mod
    for togo in child[cur]:
        if not went[togo]:
            went[togo] = True
            queue.append(togo)
print(ans)

Buggy submission (verdict: Runtime Error):
from collections import deque
import math
mod = 10**9+7
N,K = map(int,input().split())

#KPxの計算用。一回だけ使う
def Perm(n,r):#aPb
    return math.factorial(n) // math.factorial(n - r)

#K-2Pxの計算のメモ化
K_2perm =[1,K-2]
pres = K-2
for i in range(2,K-1):
    pres = (pres*(K-1-i))%mod
    K_2perm.append(pres)

child = [[] for i in range(N)]
for hoge in range(N-1):
    a,b = [int(i)-1 for i in input().split()]#点を0-indexedになおす
    child[a].append(b)
    child[b].append(a)


ans = Perm(K,len(child[0])+1)%mod
#DFSしながら塗る
went = [False] * N
queue = deque()
queue.append(0)
went[0] = True
while queue:
    cur = queue.pop()
    for togo in child[cur]:
        if not went[togo]:
            went[togo] = True
            queue.append(togo)
            print(len(child[togo]))
            ans *= K_2perm[len(child[togo])-1]
            ans %= mod
print(ans)

Buggy submission (verdict: Runtime Error):
from collections import deque
import math
mod = 10**9+7
N,K = map(int,input().split())

#KPxの計算用。一回だけ使う
def Perm(n,r):#aPb
    return math.factorial(n) // math.factorial(n - r)

#K-2Pxの計算のメモ化
K_2perm =[1,K-2]
pres = K-2
for i in range(2,K-1):
    pres = (pres*(K-1-i))%mod
    K_2perm.append(pres)
    
child = [[] for i in range(N)]
for hoge in range(N-1):
    a,b = [int(i)-1 for i in input().split()]
    child[a].append(b)
    child[b].append(a)


ans = Perm(K,len(child[0])+1)%mod
#DFSしながら塗る
went = [False] * N
queue = deque()
queue.append(0)
went[0] = True
while queue:
    cur = queue.pop()
    for togo in child[cur]:
        if not went[togo]:
            went[togo] = True
            queue.append(togo)
            print(len(child[togo]))
            ans *= K_2perm[len(child[togo])-1]
            ans %= mod
print(ans)

Buggy submission (verdict: Runtime Error):
from collections import deque
import math
mod = 10**9+7
N,K = map(int,input().split())

def Perm(n,r):#aPb
    return math.factorial(n) // math.factorial(n - r)

K_2perm =[1,K-2]
pres = K-2
#K_2perm[i] = K-2Pi
for i in range(2,K-1):
    pres = (pres*(K-1-i))%mod
    K_2perm.append(pres)
child = [[] for i in range(N)]
for hoge in range(N-1):
    a,b = [int(i)-1 for i in input().split()]
    child[a].append(b)
    child[b].append(a)
went = [False] * N
queue = deque()
queue.append(0)
went[0] = True

ans = Perm(K,len(child[0])+1)%mod
while queue:
    cur = queue.pop()
    if cur!=0:
        ans *= K_2perm[len(child[cur])-1]
        ans %= mod
    for togo in child[cur]:
        if not went[togo]:
            went[togo] = True
            queue.append(togo)
print(ans)

Buggy submission (verdict: Runtime Error):
from collections import deque
import math
mod = 10**9+7
N,K = map(int,input().split())

def Perm(n,r):#aPb
    return math.factorial(n) // math.factorial(n - r)

K_2perm =[1,K-2]
pres = K-2
#K_2perm[i] = K-2Pi
for i in range(2,K-1):
    pres = (pres*(K-1-i))%mod
    K_2perm.append(pres)
child = [[] for i in range(N)]
for hoge in range(N-1):
    a,b = [int(i)-1 for i in input().split()]
    child[a].append(b)
    child[b].append(a)
went = [False] * N
queue = deque()
queue.append(0)
went[0] = True

ans = Perm(K,len(child[0])+1)%mod
while queue:
    cur = queue.pop()
    if cur!=0:
        ans *= K_2perm[len(child[cur])-1]
        ans %= mod
    for togo in child[cur]:
        if not went[togo]:
            went[togo] = True
            queue.append(togo)
print(ans)

Buggy submission (verdict: Runtime Error):
from collections import deque
import math
mod = 10**9+7
N,K = map(int,input().split())

def Perm(n,r):#aPb
    return math.factorial(n) // math.factorial(n - r)

K_2perm =[1,K-2]
pres = K-2
#K_2perm[i] = K-2Pi
for i in range(2,K-1):
    pres = (pres*(K-1-i))%mod
    K_2perm.append(pres)
print(K_2perm)
child = [[] for i in range(N)]
for hoge in range(N-1):
    a,b = [int(i)-1 for i in input().split()]
    child[a].append(b)
    child[b].append(a)
went = [False] * N
queue = deque()
queue.append(0)
went[0] = True

ans = Perm(K,len(child[0])+1)%mod
while queue:
    cur = queue.pop()
    ans *= K_2perm[len(child[cur])-1]
    for togo in child[cur]:
        if not went[togo]:
            went[togo] = True
            queue.append(togo)
print(ans)