Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

# -*- coding: utf-8 -*-


class FactMod():
    '''
    modの値が素数の時のfactと組み合わせを求める
    フェルマーの小定理を用いているため、modが素数以外の時は使えない
    '''

    def __init__(self, n, mod):
        '''
        コンストラクタ
        f:nまでの i!の値を　配列に入れる
        inv: (i!)^-1　の値を配列に入れる
        '''
        self.mod = mod
        self.f = [1]*(n+1)
        for i in range(1, n+1):
            self.f[i] = self.f[i-1]*i % mod

        self.inv = [pow(self.f[-1], mod-2, mod)]
        for i in range(1, n+1)[::-1]:
            self.inv.append(self.inv[-1]*i % mod)
        self.inv.reverse()

    def fact(self, n):
        '''
        n!の値を返す
        '''
        return self.f[n]

    def comb(self, n, r):
        '''
        nCrの値を返す
        '''
        ret = self.f[n] * self.inv[n-r]*self.inv[r]
        ret %= self.mod
        return ret

    def perm(self, a, b):
        if a < b or a < 0 or b < 0:
            return 0
        ret = self.f[a]*self.inv[a-b]
        ret %= self.mod
        return ret


MOD = 10**9+7
N, K = map(int, input().split())
edges = [list(map(lambda x:int(x)-1, input().split())) for _ in range(N-1)]
adj = [[] for _ in range(N)]

F = FactMod(N, MOD)

for a, b in edges:
    adj[a].append(b)
    adj[b].append(a)

# current parent
Q = []
for a in adj[0]:
    Q.append((a, 0))
ans = F.perm(K, len(adj[0])+1)
ans %= MOD

while Q:
    current, prev = Q.pop()
    child = len(adj[current])-1
    ret = F.perm(K-2, child)
    ans *= ret
    ans %= MOD
    for a in adj[current]:
        if a == prev:
            continue
        else:
            Q.append((a, current))
print(ans)


Fixed submission:
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

# -*- coding: utf-8 -*-


class FactMod():
    '''
    modの値が素数の時のfactと組み合わせを求める
    フェルマーの小定理を用いているため、modが素数以外の時は使えない
    '''

    def __init__(self, n, mod):
        '''
        コンストラクタ
        f:nまでの i!の値を　配列に入れる
        inv: (i!)^-1　の値を配列に入れる
        '''
        self.mod = mod
        self.f = [1]*(n+1)
        for i in range(1, n+1):
            self.f[i] = self.f[i-1]*i % mod

        self.inv = [pow(self.f[-1], mod-2, mod)]
        for i in range(1, n+1)[::-1]:
            self.inv.append(self.inv[-1]*i % mod)
        self.inv.reverse()

    def perm(self, a, b):
        if a < b or a < 0 or b < 0:
            return 0
        ret = self.f[a]*self.inv[a-b]
        ret %= self.mod
        return ret


MOD = 10**9+7
N, K = map(int, input().split())
edges = [list(map(lambda x:int(x)-1, input().split())) for _ in range(N-1)]
adj = [[] for _ in range(N)]

F = FactMod(K+1, MOD)

for a, b in edges:
    adj[a].append(b)
    adj[b].append(a)

# current parent
Q = []
for a in adj[0]:
    Q.append((a, 0))
ans = F.perm(K, len(adj[0])+1)
ans %= MOD

while Q:
    current, prev = Q.pop()
    child = len(adj[current])-1
    ret = F.perm(K-2, child)
    ans *= ret
    ans %= MOD
    for a in adj[current]:
        if a == prev:
            continue
        else:
            Q.append((a, current))
print(ans)

Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

# -*- coding: utf-8 -*-


class FactMod():
    '''
    modの値が素数の時のfactと組み合わせを求める
    フェルマーの小定理を用いているため、modが素数以外の時は使えない
    '''

    def __init__(self, n, mod):
        '''
        コンストラクタ
        f:nまでの i!の値を　配列に入れる
        inv: (i!)^-1　の値を配列に入れる
        '''
        self.mod = mod
        self.f = [1]*(n+1)
        for i in range(1, n+1):
            self.f[i] = self.f[i-1]*i % mod

        self.inv = [pow(self.f[-1], mod-2, mod)]
        for i in range(1, n+1)[::-1]:
            self.inv.append(self.inv[-1]*i % mod)
        self.inv.reverse()

    def fact(self, n):
        '''
        n!の値を返す
        '''
        return self.f[n]

    def comb(self, n, r):
        '''
        nCrの値を返す
        '''
        ret = self.f[n] * self.inv[n-r]*self.inv[r]
        ret %= self.mod
        return ret

    def perm(self, a, b):
        if a < b:
            return 0
        ret = self.f[a]*self.inv[a-b]
        ret %= self.mod
        return ret


MOD = 10**9+7
N, K = map(int, input().split())
edges = [list(map(lambda x:int(x)-1, input().split())) for _ in range(N-1)]
adj = [[] for _ in range(N)]

F = FactMod(N, MOD)

for a, b in edges:
    adj[a].append(b)
    adj[b].append(a)

# current parent
Q = []
for a in adj[0]:
    Q.append((a, 0))
ans = F.perm(K, len(adj[0])+1)
ans %= MOD

while Q:
    current, prev = Q.pop()
    child = len(adj[current])-1
    ret = F.perm(K-2, child)
    ans *= ret

    ans %= MOD
    for a in adj[current]:
        if a == prev:
            continue
        else:
            Q.append((a, current))
print(ans)


Fixed submission:
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

# -*- coding: utf-8 -*-


class FactMod():
    '''
    modの値が素数の時のfactと組み合わせを求める
    フェルマーの小定理を用いているため、modが素数以外の時は使えない
    '''

    def __init__(self, n, mod):
        '''
        コンストラクタ
        f:nまでの i!の値を　配列に入れる
        inv: (i!)^-1　の値を配列に入れる
        '''
        self.mod = mod
        self.f = [1]*(n+1)
        for i in range(1, n+1):
            self.f[i] = self.f[i-1]*i % mod

        self.inv = [pow(self.f[-1], mod-2, mod)]
        for i in range(1, n+1)[::-1]:
            self.inv.append(self.inv[-1]*i % mod)
        self.inv.reverse()

    def perm(self, a, b):
        if a < b or a < 0 or b < 0:
            return 0
        ret = self.f[a]*self.inv[a-b]
        ret %= self.mod
        return ret


MOD = 10**9+7
N, K = map(int, input().split())
edges = [list(map(lambda x:int(x)-1, input().split())) for _ in range(N-1)]
adj = [[] for _ in range(N)]

F = FactMod(K+1, MOD)

for a, b in edges:
    adj[a].append(b)
    adj[b].append(a)

# current parent
Q = []
for a in adj[0]:
    Q.append((a, 0))
ans = F.perm(K, len(adj[0])+1)
ans %= MOD

while Q:
    current, prev = Q.pop()
    child = len(adj[current])-1
    ret = F.perm(K-2, child)
    ans *= ret
    ans %= MOD
    for a in adj[current]:
        if a == prev:
            continue
        else:
            Q.append((a, current))
print(ans)

Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

# -*- coding: utf-8 -*-


class FactMod():
    '''
    modの値が素数の時のfactと組み合わせを求める
    フェルマーの小定理を用いているため、modが素数以外の時は使えない
    '''

    def __init__(self, n, mod):
        '''
        コンストラクタ
        f:nまでの i!の値を　配列に入れる
        inv: (i!)^-1　の値を配列に入れる
        '''
        self.mod = mod
        self.f = [1]*(n+1)
        for i in range(1, n+1):
            self.f[i] = self.f[i-1]*i % mod

        self.inv = [pow(self.f[-1], mod-2, mod)]
        for i in range(1, n+1)[::-1]:
            self.inv.append(self.inv[-1]*i % mod)
        self.inv.reverse()

    def fact(self, n):
        '''
        n!の値を返す
        '''
        return self.f[n]

    def comb(self, n, r):
        '''
        nCrの値を返す
        '''
        ret = self.f[n] * self.inv[n-r]*self.inv[r]
        ret %= self.mod
        return ret

    def perm(self, a, b):
        ret = self.f[a]*self.inv[a-b]
        ret %= self.mod
        return ret


MOD = 10**9+7
N, K = map(int, input().split())
edges = [list(map(lambda x:int(x)-1, input().split())) for _ in range(N-1)]
adj = [[] for _ in range(N)]

F = FactMod(N, MOD)

for a, b in edges:
    adj[a].append(b)
    adj[b].append(a)

# current parent
Q = []
for a in adj[0]:
    Q.append((a, 0))
ans = F.perm(K, len(adj[0])+1)
ans %= MOD

while Q:
    current, prev = Q.pop()
    child = len(adj[current])-1
    ret = F.perm(K-2, child)
    ans *= ret

    ans %= MOD
    for a in adj[current]:
        if a == prev:
            continue
        else:
            Q.append((a, current))
print(ans)


Fixed submission:
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

# -*- coding: utf-8 -*-


class FactMod():
    '''
    modの値が素数の時のfactと組み合わせを求める
    フェルマーの小定理を用いているため、modが素数以外の時は使えない
    '''

    def __init__(self, n, mod):
        '''
        コンストラクタ
        f:nまでの i!の値を　配列に入れる
        inv: (i!)^-1　の値を配列に入れる
        '''
        self.mod = mod
        self.f = [1]*(n+1)
        for i in range(1, n+1):
            self.f[i] = self.f[i-1]*i % mod

        self.inv = [pow(self.f[-1], mod-2, mod)]
        for i in range(1, n+1)[::-1]:
            self.inv.append(self.inv[-1]*i % mod)
        self.inv.reverse()

    def perm(self, a, b):
        if a < b or a < 0 or b < 0:
            return 0
        ret = self.f[a]*self.inv[a-b]
        ret %= self.mod
        return ret


MOD = 10**9+7
N, K = map(int, input().split())
edges = [list(map(lambda x:int(x)-1, input().split())) for _ in range(N-1)]
adj = [[] for _ in range(N)]

F = FactMod(K+1, MOD)

for a, b in edges:
    adj[a].append(b)
    adj[b].append(a)

# current parent
Q = []
for a in adj[0]:
    Q.append((a, 0))
ans = F.perm(K, len(adj[0])+1)
ans %= MOD

while Q:
    current, prev = Q.pop()
    child = len(adj[current])-1
    ret = F.perm(K-2, child)
    ans *= ret
    ans %= MOD
    for a in adj[current]:
        if a == prev:
            continue
        else:
            Q.append((a, current))
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from math import factorial
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


def p(a, b):
    if a < b:
        return 0
    return factorial(a)//factorial(a-b)


MOD = 10**9+7
N, K = map(int, input().split())
edges = [list(map(lambda x:int(x)-1, input().split())) for _ in range(N-1)]
adj = [[] for _ in range(N)]

for a, b in edges:
    adj[a].append(b)
    adj[b].append(a)

# current parent
Q = []
for a in adj[0]:
    Q.append((a, 0))
ans = p(K, len(adj[0])+1)
ans %= MOD

while Q:
    current, prev = Q.pop()
    child = len(adj[current])-1
    ret = p(K-2, child)
    ans *= ret

    ans %= MOD
    for a in adj[current]:
        if a == prev:
            continue
        else:
            Q.append((a, current))
print(ans)


Fixed submission:
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

# -*- coding: utf-8 -*-


class FactMod():
    '''
    modの値が素数の時のfactと組み合わせを求める
    フェルマーの小定理を用いているため、modが素数以外の時は使えない
    '''

    def __init__(self, n, mod):
        '''
        コンストラクタ
        f:nまでの i!の値を　配列に入れる
        inv: (i!)^-1　の値を配列に入れる
        '''
        self.mod = mod
        self.f = [1]*(n+1)
        for i in range(1, n+1):
            self.f[i] = self.f[i-1]*i % mod

        self.inv = [pow(self.f[-1], mod-2, mod)]
        for i in range(1, n+1)[::-1]:
            self.inv.append(self.inv[-1]*i % mod)
        self.inv.reverse()

    def perm(self, a, b):
        if a < b or a < 0 or b < 0:
            return 0
        ret = self.f[a]*self.inv[a-b]
        ret %= self.mod
        return ret


MOD = 10**9+7
N, K = map(int, input().split())
edges = [list(map(lambda x:int(x)-1, input().split())) for _ in range(N-1)]
adj = [[] for _ in range(N)]

F = FactMod(K+1, MOD)

for a, b in edges:
    adj[a].append(b)
    adj[b].append(a)

# current parent
Q = []
for a in adj[0]:
    Q.append((a, 0))
ans = F.perm(K, len(adj[0])+1)
ans %= MOD

while Q:
    current, prev = Q.pop()
    child = len(adj[current])-1
    ret = F.perm(K-2, child)
    ans *= ret
    ans %= MOD
    for a in adj[current]:
        if a == prev:
            continue
        else:
            Q.append((a, current))
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from math import factorial
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


def p(a, b):
    if a < b:
        return 0
    return factorial(a)//factorial(a-b)


MOD = 10**9+7
N, K = map(int, input().split())
edges = [list(map(lambda x:int(x)-1, input().split())) for _ in range(N-1)]
adj = [[] for _ in range(N)]

for a, b in edges:
    adj[a].append(b)
    adj[b].append(a)

# current parent
Q = []
for a in adj[0]:
    Q.append((a, 0))
ans = p(K, len(adj[0])+1)
ans %= MOD

while Q:
    current, prev = Q.pop()
    child = len(adj[current])-1
    ret = p(K-2, child)
    ans *= ret

    ans %= MOD
    for a in adj[current]:
        if a == prev:
            continue
        else:
            Q.append((a, current))
print(ans)


Fixed submission:
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

# -*- coding: utf-8 -*-


class FactMod():
    '''
    modの値が素数の時のfactと組み合わせを求める
    フェルマーの小定理を用いているため、modが素数以外の時は使えない
    '''

    def __init__(self, n, mod):
        '''
        コンストラクタ
        f:nまでの i!の値を　配列に入れる
        inv: (i!)^-1　の値を配列に入れる
        '''
        self.mod = mod
        self.f = [1]*(n+1)
        for i in range(1, n+1):
            self.f[i] = self.f[i-1]*i % mod

        self.inv = [pow(self.f[-1], mod-2, mod)]
        for i in range(1, n+1)[::-1]:
            self.inv.append(self.inv[-1]*i % mod)
        self.inv.reverse()

    def perm(self, a, b):
        if a < b or a < 0 or b < 0:
            return 0
        ret = self.f[a]*self.inv[a-b]
        ret %= self.mod
        return ret


MOD = 10**9+7
N, K = map(int, input().split())
edges = [list(map(lambda x:int(x)-1, input().split())) for _ in range(N-1)]
adj = [[] for _ in range(N)]

F = FactMod(K+1, MOD)

for a, b in edges:
    adj[a].append(b)
    adj[b].append(a)

# current parent
Q = []
for a in adj[0]:
    Q.append((a, 0))
ans = F.perm(K, len(adj[0])+1)
ans %= MOD

while Q:
    current, prev = Q.pop()
    child = len(adj[current])-1
    ret = F.perm(K-2, child)
    ans *= ret
    ans %= MOD
    for a in adj[current]:
        if a == prev:
            continue
        else:
            Q.append((a, current))
print(ans)

Buggy python submission (verdict: Runtime Error):
from math import factorial
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


def p(a, b):
    return factorial(a)//factorial(a-b)


MOD = 10**9+7
N, K = map(int, input().split())
edges = [list(map(lambda x:int(x)-1, input().split())) for _ in range(N-1)]
adj = [[] for _ in range(N)]

for a, b in edges:
    adj[a].append(b)
    adj[b].append(a)

# current parent
Q = []
for a in adj[0]:
    Q.append((a, 0))
ans = p(K, len(adj[0])+1)
ans %= MOD

while Q:
    current, prev = Q.pop()
    child = len(adj[current])-1
    ret = p(K-2, child)
    ans *= ret

    ans %= MOD
    for a in adj[current]:
        if a == prev:
            continue
        else:
            Q.append((a, current))
print(ans)


Fixed submission:
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

# -*- coding: utf-8 -*-


class FactMod():
    '''
    modの値が素数の時のfactと組み合わせを求める
    フェルマーの小定理を用いているため、modが素数以外の時は使えない
    '''

    def __init__(self, n, mod):
        '''
        コンストラクタ
        f:nまでの i!の値を　配列に入れる
        inv: (i!)^-1　の値を配列に入れる
        '''
        self.mod = mod
        self.f = [1]*(n+1)
        for i in range(1, n+1):
            self.f[i] = self.f[i-1]*i % mod

        self.inv = [pow(self.f[-1], mod-2, mod)]
        for i in range(1, n+1)[::-1]:
            self.inv.append(self.inv[-1]*i % mod)
        self.inv.reverse()

    def perm(self, a, b):
        if a < b or a < 0 or b < 0:
            return 0
        ret = self.f[a]*self.inv[a-b]
        ret %= self.mod
        return ret


MOD = 10**9+7
N, K = map(int, input().split())
edges = [list(map(lambda x:int(x)-1, input().split())) for _ in range(N-1)]
adj = [[] for _ in range(N)]

F = FactMod(K+1, MOD)

for a, b in edges:
    adj[a].append(b)
    adj[b].append(a)

# current parent
Q = []
for a in adj[0]:
    Q.append((a, 0))
ans = F.perm(K, len(adj[0])+1)
ans %= MOD

while Q:
    current, prev = Q.pop()
    child = len(adj[current])-1
    ret = F.perm(K-2, child)
    ans *= ret
    ans %= MOD
    for a in adj[current]:
        if a == prev:
            continue
        else:
            Q.append((a, current))
print(ans)

Buggy python submission (verdict: Runtime Error):
from math import factorial
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


def p(a, b):
    return factorial(a)//factorial(a-b)


MOD = 10**9+7
N, K = map(int, input().split())
edges = [list(map(lambda x:int(x)-1, input().split())) for _ in range(N-1)]
adj = [[] for _ in range(N)]

for a, b in edges:
    adj[a].append(b)
    adj[b].append(a)

# current parent
Q = []
for a in adj[0]:
    Q.append((a, 0))
ans = p(K, len(adj[0])+1)
ans %= MOD

while Q:
    current, prev = Q.pop()
    child = len(adj[current])-1
    ret = p(K-2, child)
    ans *= ret

    ans %= MOD
    for a in adj[current]:
        if a == prev:
            continue
        else:
            Q.append((a, current))
print(ans)


Fixed submission:
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

# -*- coding: utf-8 -*-


class FactMod():
    '''
    modの値が素数の時のfactと組み合わせを求める
    フェルマーの小定理を用いているため、modが素数以外の時は使えない
    '''

    def __init__(self, n, mod):
        '''
        コンストラクタ
        f:nまでの i!の値を　配列に入れる
        inv: (i!)^-1　の値を配列に入れる
        '''
        self.mod = mod
        self.f = [1]*(n+1)
        for i in range(1, n+1):
            self.f[i] = self.f[i-1]*i % mod

        self.inv = [pow(self.f[-1], mod-2, mod)]
        for i in range(1, n+1)[::-1]:
            self.inv.append(self.inv[-1]*i % mod)
        self.inv.reverse()

    def perm(self, a, b):
        if a < b or a < 0 or b < 0:
            return 0
        ret = self.f[a]*self.inv[a-b]
        ret %= self.mod
        return ret


MOD = 10**9+7
N, K = map(int, input().split())
edges = [list(map(lambda x:int(x)-1, input().split())) for _ in range(N-1)]
adj = [[] for _ in range(N)]

F = FactMod(K+1, MOD)

for a, b in edges:
    adj[a].append(b)
    adj[b].append(a)

# current parent
Q = []
for a in adj[0]:
    Q.append((a, 0))
ans = F.perm(K, len(adj[0])+1)
ans %= MOD

while Q:
    current, prev = Q.pop()
    child = len(adj[current])-1
    ret = F.perm(K-2, child)
    ans *= ret
    ans %= MOD
    for a in adj[current]:
        if a == prev:
            continue
        else:
            Q.append((a, current))
print(ans)