Buggy python submission (verdict: Time Limit Exceeded):
N, K = list(map(int, input().split()))
links = [list(map(int, input().split())) for _ in range(N-1)]

def perm(a, b):
    s = 1
    for i in range(a-b+1, a+1):
        s *= i
    return s

def main():
    if N == 1:
        return K
    d = {i: set() for i in range(1, N+1)}
    for i, j in links:
        d[i].add(j)
        d[j].add(i)
    history = {1}
    stack = d[1]
    b = len(stack)
    if K - 1 < b:
        return 0
    d.pop(1)
    ans = K * perm(K - 1, b)
    a = K - 2
    lim = max([len(x) for x in d.values()])
    if lim - 1 > a:
        return 0
    lim += 1
    perm_list = [None] * lim
    perm_list[0] = 1
    for i in range(1, lim):
        perm_list[i] = perm_list[i-1] * (a + 1 - i)
    while stack:
        node = stack.pop()
        if node in history:
            continue
        history.add(node)
        ans *= perm_list[len(d[node]) - 1]
        ans %= 1000000007
        stack |= d[node]
    return ans
    
print(main())


Fixed submission:
N, K = list(map(int, input().split()))
l = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    a, b = list(map(int, input().split()))
    l[a].append(b)
    l[b].append(a)

deg1 = [0] * (N + 1)
deg2 = [0] * (N + 1)
history = [True] * (N + 1)
stack = [1]
ans = 1

while stack:
    node = stack.pop()
    ans *= K - deg1[node] - deg2[node]
    ans %= 1000000007
    history[node] = False
    for child in l[node]:
        if history[child]:
            deg1[child] += 1
            deg2[child] += deg1[node]
            deg1[node] += 1
            stack.append(child)
            
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N, K = list(map(int, input().split()))
links = [list(map(int, input().split())) for _ in range(N-1)]

def perm(a, b):
    s = 1
    for i in range(a-b+1, a+1):
        s *= i
    return s

if N == 1:
    print(K)
else:
    mod = 1000000007
    d = {i: set() for i in range(1, N+1)}
    for i, j in links:
        d[i].add(j)
        d[j].add(i)
    b = len(d[1])
    if K - 1 < b:
        print(0)
    else:
        ans = K * perm(K - 1, b)
        root = d[1]
        history = [1]
        a = K - 2
        while True:
            children = set()
            for i in list(root):
                b = len(d[i]) - 1
                if a < b:
                    print(0)
                    break
                children |= d[i]
                if b == 0:
                    continue
                ans *= perm(a, b)
                ans %= mod
            else:
                for i in history:
                    if i in children:
                        children.remove(i)
                if len(children) == 0:
                    print(ans % mod)
                    break
                history, root = root, children
                continue
            break


Fixed submission:
N, K = list(map(int, input().split()))
l = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    a, b = list(map(int, input().split()))
    l[a].append(b)
    l[b].append(a)

deg1 = [0] * (N + 1)
deg2 = [0] * (N + 1)
history = [True] * (N + 1)
stack = [1]
ans = 1

while stack:
    node = stack.pop()
    ans *= K - deg1[node] - deg2[node]
    ans %= 1000000007
    history[node] = False
    for child in l[node]:
        if history[child]:
            deg1[child] += 1
            deg2[child] += deg1[node]
            deg1[node] += 1
            stack.append(child)
            
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N, K = list(map(int, input().split()))
links = [list(map(int, input().split())) for _ in range(N-1)]

def perm(a, b):
    s = 1
    for i in range(a-b+1, a+1):
        s *= i
    return s

if N == 1:
    print(K)
else:
    mod = 1000000007
    d = {i: set() for i in range(1, N+1)}
    for i, j in links:
        d[i].add(j)
        d[j].add(i)
    b = len(d[1])
    if K - 1 < b:
        print(0)
    else:
        ans = K * perm(K - 1, b)
        root = d[1]
        history = [1]
        a = K - 2
        while True:
            children = set()
            for i in list(root):
                b = len(d[i]) - 1
                if a < b:
                    print(0)
                    break
                children |= d[i]
                if b == 0:
                    continue
                ans *= perm(a, b)
            else:
                for i in history:
                    if i in children:
                        children.remove(i)
                if len(children) == 0:
                    print(ans % mod)
                    break
                history, root = root, children
                continue
            break


Fixed submission:
N, K = list(map(int, input().split()))
l = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    a, b = list(map(int, input().split()))
    l[a].append(b)
    l[b].append(a)

deg1 = [0] * (N + 1)
deg2 = [0] * (N + 1)
history = [True] * (N + 1)
stack = [1]
ans = 1

while stack:
    node = stack.pop()
    ans *= K - deg1[node] - deg2[node]
    ans %= 1000000007
    history[node] = False
    for child in l[node]:
        if history[child]:
            deg1[child] += 1
            deg2[child] += deg1[node]
            deg1[node] += 1
            stack.append(child)
            
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N, K = list(map(int, input().split()))
links = [list(map(int, input().split())) for _ in range(N-1)]

def perm(a, b):
    s = 1
    for i in range(a-b+1, a+1):
        s *= i
    return s

if N == 1:
    print(K)
elif K == 1:
    print(0)
else:
    mod = 1000000007
    d = {}
    for a, b in links:
        if a in d:
            d[a].append(b)
        else:
            d[a] = [b]
        if b in d:
            d[b].append(a)
        else:
            d[b] = [a]
    for j in d[1]:
        d[j].remove(1)
    ans = K * perm(K - 1, len(d[1]))
    root = d[1]
    a = K - 2
    while True:
        children = []
        for i in root:
            for j in d[i]:
                d[j].remove(i)
            b = len(d[i])
            if a < b:
                print(0)
                break
            if b == 0:
                continue
            ans *= perm(a, b)
            ans %= 1000000007
            children.extend(d[i])
        else:
            if children == []:
                print(ans % mod)
                break
            root = children
            continue
        break


Fixed submission:
N, K = list(map(int, input().split()))
l = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    a, b = list(map(int, input().split()))
    l[a].append(b)
    l[b].append(a)

deg1 = [0] * (N + 1)
deg2 = [0] * (N + 1)
history = [True] * (N + 1)
stack = [1]
ans = 1

while stack:
    node = stack.pop()
    ans *= K - deg1[node] - deg2[node]
    ans %= 1000000007
    history[node] = False
    for child in l[node]:
        if history[child]:
            deg1[child] += 1
            deg2[child] += deg1[node]
            deg1[node] += 1
            stack.append(child)
            
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N, K = list(map(int, input().split()))
l = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    a, b = list(map(int, input().split()))
    l[a].append(b)
    l[b].append(a)

deg1 = [0] * (N + 1)
deg2 = [0] * (N + 1)
history = [True] * (N + 1)
stack = [1]
ans = 1

while stack:
    node = stack.pop()
    ans *= K - deg1[node] - deg2[node]
    history[node] = False
    for child in l[node]:
        if history[child]:
            deg1[child] += 1
            deg2[child] += deg1[node]
            deg1[node] += 1
            stack.append(child)
            
print(ans % 1000000007)

Fixed submission:
N, K = list(map(int, input().split()))
l = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    a, b = list(map(int, input().split()))
    l[a].append(b)
    l[b].append(a)

deg1 = [0] * (N + 1)
deg2 = [0] * (N + 1)
history = [True] * (N + 1)
stack = [1]
ans = 1

while stack:
    node = stack.pop()
    ans *= K - deg1[node] - deg2[node]
    ans %= 1000000007
    history[node] = False
    for child in l[node]:
        if history[child]:
            deg1[child] += 1
            deg2[child] += deg1[node]
            deg1[node] += 1
            stack.append(child)
            
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N, K = list(map(int, input().split()))
links = [list(map(int, input().split())) for _ in range(N-1)]

def perm(a, b):
    s = 1
    for i in range(a-b+1, a+1):
        s *= i
    return s

def main():
    if N == 1:
        return K
    d = {i: set() for i in range(1, N+1)}
    for i, j in links:
        d[i].add(j)
        d[j].add(i)
    history = {1}
    stack = d[1]
    b = len(stack)
    if K - 1 < b:
        return 0
    d.pop(1)
    ans = K * perm(K - 1, b)
    a = K - 2
    lim = max([len(x) for x in d.values()])
    if lim - 1 > a:
        return 0
    lim += 1
    perm_list = [None] * lim
    perm_list[0] = 1
    for i in range(1, lim):
        perm_list[i] = perm_list[i-1] * (a + 1 - i)
    while stack:
        node = stack.pop()
        history.add(node)
        ans *= perm_list[len(d[node]) - 1]
        for i in d[node]:
            if i not in history:
                stack.add(i)
    return ans
    
print(main() % 1000000007)

Fixed submission:
N, K = list(map(int, input().split()))
l = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    a, b = list(map(int, input().split()))
    l[a].append(b)
    l[b].append(a)

deg1 = [0] * (N + 1)
deg2 = [0] * (N + 1)
history = [True] * (N + 1)
stack = [1]
ans = 1

while stack:
    node = stack.pop()
    ans *= K - deg1[node] - deg2[node]
    ans %= 1000000007
    history[node] = False
    for child in l[node]:
        if history[child]:
            deg1[child] += 1
            deg2[child] += deg1[node]
            deg1[node] += 1
            stack.append(child)
            
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N, K = list(map(int, input().split()))
links = [list(map(int, input().split())) for _ in range(N-1)]

def perm(a, b):
    s = 1
    for i in range(a-b+1, a+1):
        s *= i
    return s

def main():
    if N == 1:
        return K
    d = {i: set() for i in range(1, N+1)}
    for i, j in links:
        d[i].add(j)
        d[j].add(i)
    history = {1}
    stack = d[1]
    b = len(stack)
    if K - 1 < b:
        return 0
    d.pop(1)
    ans = K * perm(K - 1, b)
    a = K - 2
    lim = max([len(x) for x in d.values()])
    if lim - 1 > a:
        return 0
    lim += 1
    perm_list = [None] * lim
    perm_list[0] = 1
    for i in range(1, lim):
        perm_list[i] = perm_list[i-1] * (a + 1 - i)
    while stack:
        node = stack.pop()
        if node in history:
            continue
        history.add(node)
        ans *= perm_list[len(d[node]) - 1]
        stack |= d[node]
    return ans
    
print(main() % 1000000007)

Fixed submission:
N, K = list(map(int, input().split()))
l = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    a, b = list(map(int, input().split()))
    l[a].append(b)
    l[b].append(a)

deg1 = [0] * (N + 1)
deg2 = [0] * (N + 1)
history = [True] * (N + 1)
stack = [1]
ans = 1

while stack:
    node = stack.pop()
    ans *= K - deg1[node] - deg2[node]
    ans %= 1000000007
    history[node] = False
    for child in l[node]:
        if history[child]:
            deg1[child] += 1
            deg2[child] += deg1[node]
            deg1[node] += 1
            stack.append(child)
            
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N, K = list(map(int, input().split()))
links = [list(map(int, input().split())) for _ in range(N-1)]

def perm(a, b):
    s = 1
    for i in range(a-b+1, a+1):
        s *= i
    return s

def main():
    if N == 1:
        return K
    d = {i: set() for i in range(1, N+1)}
    for i, j in links:
        d[i].add(j)
        d[j].add(i)
    for v in d[1]:
        d[v].remove(1)
    stack = d[1]
    b = len(stack)
    if K - 1 < b:
        return 0
    d.pop(1)
    ans = K * perm(K - 1, b)
    a = K - 2
    lim = max([len(x) for x in d.values()])
    if lim - 1 > a:
        return 0
    lim += 1
    perm_list = [None] * lim
    perm_list[0] = 1
    for i in range(1, lim):
        perm_list[i] = perm_list[i-1] * (a + 1 - i)
    while stack:
        node = stack.pop()
        for v in d[node]:
            d[v].remove(node)
        ans *= perm_list[len(d[node])]
        stack |= d[node]
    return ans
    
print(main() % 1000000007)

Fixed submission:
N, K = list(map(int, input().split()))
l = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    a, b = list(map(int, input().split()))
    l[a].append(b)
    l[b].append(a)

deg1 = [0] * (N + 1)
deg2 = [0] * (N + 1)
history = [True] * (N + 1)
stack = [1]
ans = 1

while stack:
    node = stack.pop()
    ans *= K - deg1[node] - deg2[node]
    ans %= 1000000007
    history[node] = False
    for child in l[node]:
        if history[child]:
            deg1[child] += 1
            deg2[child] += deg1[node]
            deg1[node] += 1
            stack.append(child)
            
print(ans)

Buggy python submission (verdict: Runtime Error):
N, K = list(map(int, input().split()))
links = [list(map(int, input().split())) for _ in range(N-1)]

def perm(a, b):
    s = 1
    for i in range(a-b+1, a+1):
        s *= i
    return s

if N == 1:
    ans = K
else:
    perm_dict = {}
    mod = 1000000007
    d = {i: set() for i in range(1, N+1)}
    history = [True] * (N + 1)
    for i, j in links:
        d[i].add(j)
        d[j].add(i)
    for v in d[1]:
        d[v].remove(1)
    b = len(d[1])
    if K - 1 < b:
        ans = 0
    else:
        ans = K * perm(K - 1, b)
        history[1] = False
        a = K - 2
        stack = d[1]
        while stack:
            node = stack.pop()
            for v in d[node]:
                d[v].remove(node)
            b = len(d[node])
            if a < b:
                ans = 0
                break
            if b not in perm_dict:
                perm_dict[b] = perm(a, b)
            ans *= perm_dict[b]
            stack |= d[node]
            
print(ans % mod)

Fixed submission:
N, K = list(map(int, input().split()))
l = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    a, b = list(map(int, input().split()))
    l[a].append(b)
    l[b].append(a)

deg1 = [0] * (N + 1)
deg2 = [0] * (N + 1)
history = [True] * (N + 1)
stack = [1]
ans = 1

while stack:
    node = stack.pop()
    ans *= K - deg1[node] - deg2[node]
    ans %= 1000000007
    history[node] = False
    for child in l[node]:
        if history[child]:
            deg1[child] += 1
            deg2[child] += deg1[node]
            deg1[node] += 1
            stack.append(child)
            
print(ans)

Buggy python submission (verdict: Runtime Error):
N, K = list(map(int, input().split()))
links = [list(map(int, input().split())) for _ in range(N-1)]

def perm(a, b):
    s = 1
    for i in range(a-b+1, a+1):
        s *= i
    return s

if N == 1:
    ans = K
else:
    perm_dict = {}
    mod = 1000000007
    d = {i: [] for i in range(1, N+1)}
    history = [True] * (N + 1)
    for i, j in links:
        d[i].append(j)
        d[j].append(i)
    b = len(d[1])
    if K - 1 < b:
        ans = 0
    else:
        ans = K * perm(K - 1, b)
        history[1] = False
        a = K - 2
        stack = d[1]
        while stack:
            node = stack.pop()
            history[node] = False
            b = len(d[node]) - 1
            if a < b:
                ans = 0
                break
            if b not in perm_dict:
                perm_dict[b] = perm(a, b)
            ans *= perm_dict[b]
            for i in d[node]:
                if history[i]:
                    stack.append(i)
            
print(ans % mod)

Fixed submission:
N, K = list(map(int, input().split()))
l = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    a, b = list(map(int, input().split()))
    l[a].append(b)
    l[b].append(a)

deg1 = [0] * (N + 1)
deg2 = [0] * (N + 1)
history = [True] * (N + 1)
stack = [1]
ans = 1

while stack:
    node = stack.pop()
    ans *= K - deg1[node] - deg2[node]
    ans %= 1000000007
    history[node] = False
    for child in l[node]:
        if history[child]:
            deg1[child] += 1
            deg2[child] += deg1[node]
            deg1[node] += 1
            stack.append(child)
            
print(ans)

Buggy python submission (verdict: Runtime Error):
N, K = list(map(int, input().split()))
links = [list(map(int, input().split())) for _ in range(N-1)]

def perm(a, b):
    s = 1
    for i in range(a-b+1, a+1):
        s *= i
    return s

if N == 1:
    ans = K
else:
    perm_dict = {}
    mod = 1000000007
    d = {i: [[], True] for i in range(1, N+1)}
    for i, j in links:
        d[i][0].append(j)
        d[j][0].append(i)
    b = len(d[1][0]) - 1
    if K - 1 < b:
        ans = 0
    else:
        ans = K * perm(K - 1, b)
        d[1][1] = False
        a = K - 2
        stack = d[1][0]
        while stack:
            node = stack.pop()
            d[node][1] = False
            b = len(d[node][0]) - 1
            if a < b:
                ans = 0
                break
            if b not in perm_dict:
                perm_dict[b] = perm(a, b)
            ans *= perm_dict[b]
            for i in d[node][0]:
                if d[i][1]:
                    stack.append(i)
            
print(ans % mod)

Fixed submission:
N, K = list(map(int, input().split()))
l = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    a, b = list(map(int, input().split()))
    l[a].append(b)
    l[b].append(a)

deg1 = [0] * (N + 1)
deg2 = [0] * (N + 1)
history = [True] * (N + 1)
stack = [1]
ans = 1

while stack:
    node = stack.pop()
    ans *= K - deg1[node] - deg2[node]
    ans %= 1000000007
    history[node] = False
    for child in l[node]:
        if history[child]:
            deg1[child] += 1
            deg2[child] += deg1[node]
            deg1[node] += 1
            stack.append(child)
            
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N, K = list(map(int, input().split()))
links = [list(map(int, input().split())) for _ in range(N-1)]

def perm(a, b):
    s = 1
    for i in range(a-b+1, a+1):
        s *= i
    return s

if N == 1:
    print(K)
else:
    mod = 1000000007
    d = {i: [set(), False] for i in range(1, N+1)}
    for i, j in links:
        d[i][0].add(j)
        d[j][0].add(i)
    b = len(d[1][0])
    if K - 1 < b:
        print(0)
    else:
        ans = K * perm(K - 1, b)
        d[1][1] = True
        root = d[1][0]
        a = K - 2
        while True:
            children = set()
            for i in list(root):
                d[i][1] = True
                b = len(d[i][0]) - 1
                if a < b:
                    print(0)
                    break
                children |= d[i][0]
                if b == 0:
                    continue
                ans *= perm(a, b)
            else:               
                for i in list(children):
                    if d[i][1]:
                        children.remove(i)
                if len(children) == 0:
                    print(ans % mod)
                    break
                root = children
                continue
            break

Fixed submission:
N, K = list(map(int, input().split()))
l = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    a, b = list(map(int, input().split()))
    l[a].append(b)
    l[b].append(a)

deg1 = [0] * (N + 1)
deg2 = [0] * (N + 1)
history = [True] * (N + 1)
stack = [1]
ans = 1

while stack:
    node = stack.pop()
    ans *= K - deg1[node] - deg2[node]
    ans %= 1000000007
    history[node] = False
    for child in l[node]:
        if history[child]:
            deg1[child] += 1
            deg2[child] += deg1[node]
            deg1[node] += 1
            stack.append(child)
            
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N, K = list(map(int, input().split()))
links = [list(map(int, input().split())) for _ in range(N-1)]

def perm(a, b):
    s = 1
    for i in range(a-b+1, a+1):
        s *= i
    return s

if N == 1:
    print(K)
else:
    mod = 1000000007
    d = {i: [set(), False] for i in range(1, N+1)}
    for i, j in links:
        d[i][0].add(j)
        d[j][0].add(i)
    b = len(d[1][0])
    if K - 1 < b:
        print(0)
    else:
        ans = K * perm(K - 1, b)
        d[1][1] = True
        root = d[1][0]
        a = K - 2
        while True:
            children = set()
            for i in list(root):
                d[i][1] = True
                b = len(d[i][0]) - 1
                if a < b:
                    print(0)
                    break
                children |= d[i][0]
                if b == 0:
                    continue
                ans *= perm(a, b)
            else:               
#                 for i in list(children):
#                     if d[i][1]:
#                         children.remove(i)
                if len(children) == 0:
                    print(ans % mod)
                    break
                root = children
                continue
            break

Fixed submission:
N, K = list(map(int, input().split()))
l = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    a, b = list(map(int, input().split()))
    l[a].append(b)
    l[b].append(a)

deg1 = [0] * (N + 1)
deg2 = [0] * (N + 1)
history = [True] * (N + 1)
stack = [1]
ans = 1

while stack:
    node = stack.pop()
    ans *= K - deg1[node] - deg2[node]
    ans %= 1000000007
    history[node] = False
    for child in l[node]:
        if history[child]:
            deg1[child] += 1
            deg2[child] += deg1[node]
            deg1[node] += 1
            stack.append(child)
            
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N, K = list(map(int, input().split()))
links = [list(map(int, input().split())) for _ in range(N-1)]

def perm(a, b):
    s = 1
    for i in range(a-b+1, a+1):
        s *= i
    return s

if N == 1:
    print(K)
else:
    mod = 1000000007
    d = {i: set() for i in range(1, N+1)}
    for i, j in links:
        d[i].add(j)
        d[j].add(i)
    b = len(d[1])
    if K - 1 < b:
        print(0)
    else:
        ans = K * perm(K - 1, b)
        root = d[1]
        history = [1]
        a = K - 2
        while True:
            children = set()
            for i in list(root):
                b = len(d[i]) - 1
                if a < b:
                    print(0)
                    break
                children |= d[i]
                if b == 0:
                    continue
                ans *= perm(a, b)
            else:
                for i in history:
                    if i in children:
                        children.remove(i)
                if len(children) == 0:
                    print(ans % mod)
                    break
                history, root = root, children
                continue
            break

Fixed submission:
N, K = list(map(int, input().split()))
l = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    a, b = list(map(int, input().split()))
    l[a].append(b)
    l[b].append(a)

deg1 = [0] * (N + 1)
deg2 = [0] * (N + 1)
history = [True] * (N + 1)
stack = [1]
ans = 1

while stack:
    node = stack.pop()
    ans *= K - deg1[node] - deg2[node]
    ans %= 1000000007
    history[node] = False
    for child in l[node]:
        if history[child]:
            deg1[child] += 1
            deg2[child] += deg1[node]
            deg1[node] += 1
            stack.append(child)
            
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N, K = list(map(int, input().split()))
links = [list(map(int, input().split())) for _ in range(N-1)]

def perm(a, b):
    s = 1
    for i in range(a-b+1, a+1):
        s *= i
    return s

if N == 1:
    print(K)
else:
    mod = 1000000007
    d = {i: set() for i in range(1, N+1)}
    for i, j in links:
        d[i].add(j)
        d[j].add(i)
    b = len(d[1])
    if K - 1 < b:
        print(0)
    else:
        ans = K * perm(K - 1, b)
        root = d[1]
        for i in d[1]:
            d[i].remove(1)
        a = K - 2
        while True:
            children = set()
            for i in list(root):
                for j in d[i]:
                    d[j].remove(i)
                b = len(d[i])
                if a < b:
                    print(0)
                    break
                if b == 0:
                    continue
                ans *= perm(a, b)
                children |= d[i]
            else:
                if len(children) == 0:
                    print(ans % mod)
                    break
                root = children
                continue
            break

Fixed submission:
N, K = list(map(int, input().split()))
l = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    a, b = list(map(int, input().split()))
    l[a].append(b)
    l[b].append(a)

deg1 = [0] * (N + 1)
deg2 = [0] * (N + 1)
history = [True] * (N + 1)
stack = [1]
ans = 1

while stack:
    node = stack.pop()
    ans *= K - deg1[node] - deg2[node]
    ans %= 1000000007
    history[node] = False
    for child in l[node]:
        if history[child]:
            deg1[child] += 1
            deg2[child] += deg1[node]
            deg1[node] += 1
            stack.append(child)
            
print(ans)

Buggy python submission (verdict: Runtime Error):
N, K = list(map(int, input().split()))
links = [list(map(int, input().split())) for _ in range(N-1)]

def perm(a, b):
    s = 1
    for i in range(a-b+1, a+1):
        s *= i
    return s

if N == 1:
    print(K)
else:
    mod = 1000000007
    d = {}
    for a, b in links:
        if a in d:
            d[a].append(b)
        elif b in d:
            d[b].append(a)
        else:
            d[a].append(b)
    start = links[0][0]
    b = len(d[start])
    if K - 1 < b:
        print(0)
    else:
        ans = K * perm(K - 1, b)
        root = d[start]
        a = K - 2
        while True:
            children = []
            for i in root:
                if i in d:
                    b = len(d[i])
                    if a < b:
                        print(0)
                        break
                    ans *= perm(a, b)
                    children.extend(d[i])
            else:
                if children == []:
                    print(ans % mod)
                    break
                root = children
                continue
            break

Fixed submission:
N, K = list(map(int, input().split()))
l = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    a, b = list(map(int, input().split()))
    l[a].append(b)
    l[b].append(a)

deg1 = [0] * (N + 1)
deg2 = [0] * (N + 1)
history = [True] * (N + 1)
stack = [1]
ans = 1

while stack:
    node = stack.pop()
    ans *= K - deg1[node] - deg2[node]
    ans %= 1000000007
    history[node] = False
    for child in l[node]:
        if history[child]:
            deg1[child] += 1
            deg2[child] += deg1[node]
            deg1[node] += 1
            stack.append(child)
            
print(ans)

Buggy python submission (verdict: Runtime Error):
N, K = list(map(int, input().split()))
links = [list(map(int, input().split())) for _ in range(N-1)]
start = links[0][0]

def perm(a, b):
    s = 1
    for i in range(a-b+1, a+1):
        s *= i
    return s

if N == 1:
    print(K)
else:
    mod = 1000000007
    d = {}
    for a, b in links:
        if a in d:
            d[a].append(b)
        else:
            d[a] = [b]
    b = len(d[start])
    if K - 1 < b:
        print(0)
    else:
        ans = K * perm(K - 1, b)
        root = d[start]
        a = K - 2
        while True:
            children = []
            for i in root:
                if i in d:
                    b = len(d[i])
                    if a < b:
                        print(0)
                        break
                    ans *= perm(a, b)
                    children.extend(d[i])
            else:
                if children == []:
                    print(ans % mod)
                    break
                root = children
                continue
            break

Fixed submission:
N, K = list(map(int, input().split()))
l = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    a, b = list(map(int, input().split()))
    l[a].append(b)
    l[b].append(a)

deg1 = [0] * (N + 1)
deg2 = [0] * (N + 1)
history = [True] * (N + 1)
stack = [1]
ans = 1

while stack:
    node = stack.pop()
    ans *= K - deg1[node] - deg2[node]
    ans %= 1000000007
    history[node] = False
    for child in l[node]:
        if history[child]:
            deg1[child] += 1
            deg2[child] += deg1[node]
            deg1[node] += 1
            stack.append(child)
            
print(ans)

Buggy python submission (verdict: Runtime Error):
N, K = list(map(int, input().split()))
links = [list(map(int, input().split())) for _ in range(N-1)]
start = links[0][0]

def perm(a, b):
    s = 1
    for i in range(a-b+1, a+1):
        s *= i
    return s

if N == 1:
    print(K)
# elif K - 1 < len(d[start]):
#     print(0)
else:
    mod = 1000000007
    d = {}
    for a, b in links:
        if a in d:
            d[a].append(b)
        else:
            d[a] = [b]
    ans = K * perm(K - 1, len(d[start]))
    root = d[start]
    a = K - 2
    while True:
        children = []
        for i in root:
            if i in d:
                b = len(d[i])
                if a < b:
                    print(0)
                    break
                ans *= perm(a, b)
                children.extend(d[i])
        else:
            if children == []:
                print(ans % mod)
                break
            root = children
            continue
        break

Fixed submission:
N, K = list(map(int, input().split()))
l = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    a, b = list(map(int, input().split()))
    l[a].append(b)
    l[b].append(a)

deg1 = [0] * (N + 1)
deg2 = [0] * (N + 1)
history = [True] * (N + 1)
stack = [1]
ans = 1

while stack:
    node = stack.pop()
    ans *= K - deg1[node] - deg2[node]
    ans %= 1000000007
    history[node] = False
    for child in l[node]:
        if history[child]:
            deg1[child] += 1
            deg2[child] += deg1[node]
            deg1[node] += 1
            stack.append(child)
            
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N, K = list(map(int, input().split()))
links = [list(map(int, input().split())) for _ in range(N-1)]

def perm(a, b):
    s = 1
    for i in range(a-b+1, a+1):
        s *= i
    return s

if N == 1:
    print(K)
elif K == 1:
    print(0)
else:
    mod = 1000000007
    d = {}
    for a, b in links:
        if a in d:
            d[a].append(b)
        else:
            d[a] = [b]
        if b in d:
            d[b].append(a)
        else:
            d[b] = [a]
    for j in d[1]:
        d[j].remove(1)
    ans = K * perm(K - 1, len(d[1]))
    root = d[1]
    a = K - 2
    while True:
        children = []
        for i in root:
            for j in d[i]:
                d[j].remove(i)
            b = len(d[i])
            if a < b:
                print(0)
                break
            if b == 0:
                continue
            ans *= perm(a, b)
            children.extend(d[i])
        else:
            if children == []:
                print(ans % mod)
                break
            root = children
            continue
        break


Fixed submission:
N, K = list(map(int, input().split()))
l = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    a, b = list(map(int, input().split()))
    l[a].append(b)
    l[b].append(a)

deg1 = [0] * (N + 1)
deg2 = [0] * (N + 1)
history = [True] * (N + 1)
stack = [1]
ans = 1

while stack:
    node = stack.pop()
    ans *= K - deg1[node] - deg2[node]
    ans %= 1000000007
    history[node] = False
    for child in l[node]:
        if history[child]:
            deg1[child] += 1
            deg2[child] += deg1[node]
            deg1[node] += 1
            stack.append(child)
            
print(ans)

Buggy python submission (verdict: Runtime Error):
vN, K = list(map(int, input().split()))
links = [list(map(int, input().split())) for _ in range(N-1)]

def perm(a, b):
    s = 1
    for i in range(a-b+1, a+1):
        s *= i
    return s

if N == 1:
    print(K)
elif K == 1:
    print(0)
else:
    mod = 1000000007
    d = {}
    for a, b in links:
        if a in d:
            d[a].append(b)
        else:
            d[a] = [b]
        if b in d:
            d[b].append(a)
        else:
            d[b] = [a]
    for j in d[1]:
        d[j].remove(1)
    ans = K * perm(K - 1, len(d[1]))
    root = d[1]
    a = K - 2
    while True:
        children = []
        for i in root:
            for j in d[i]:
                d[j].remove(i)
            b = len(d[i])
            if a < b:
                print(0)
                break
            if b == 0:
                continue
            ans *= perm(a, b)
            children.extend(d[i])
        else:
            if children == []:
                print(ans % mod)
                break
            root = children
            continue
        break


Fixed submission:
N, K = list(map(int, input().split()))
l = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    a, b = list(map(int, input().split()))
    l[a].append(b)
    l[b].append(a)

deg1 = [0] * (N + 1)
deg2 = [0] * (N + 1)
history = [True] * (N + 1)
stack = [1]
ans = 1

while stack:
    node = stack.pop()
    ans *= K - deg1[node] - deg2[node]
    ans %= 1000000007
    history[node] = False
    for child in l[node]:
        if history[child]:
            deg1[child] += 1
            deg2[child] += deg1[node]
            deg1[node] += 1
            stack.append(child)
            
print(ans)

Buggy python submission (verdict: Runtime Error):
N, K = list(map(int, input().split()))
links = [list(map(int, input().split())) for _ in range(N-1)]
start = links[0][0]

def perm(a, b):
    s = 1
    for i in range(a-b+1, a+1):
        s *= i
    return s

if N == 1:
    print(K)
elif K - 1 < len(d[start]):
    print(0)
else:
    mod = 1000000007
    d = {}
    for a, b in links:
        if a in d:
            d[a].append(b)
        else:
            d[a] = [b]
    ans = K * perm(K - 1, len(d[start]))
    root = d[start]
    a = K - 2
    while True:
        children = []
        for i in root:
            if i in d:
                b = len(d[i])
                if a < b:
                    print(0)
                    break
                ans *= perm(a, b)
                children.extend(d[i])
            continue
        else:
            if children == []:
                print(ans % mod)
                break
            root = children
            continue
        break

Fixed submission:
N, K = list(map(int, input().split()))
l = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    a, b = list(map(int, input().split()))
    l[a].append(b)
    l[b].append(a)

deg1 = [0] * (N + 1)
deg2 = [0] * (N + 1)
history = [True] * (N + 1)
stack = [1]
ans = 1

while stack:
    node = stack.pop()
    ans *= K - deg1[node] - deg2[node]
    ans %= 1000000007
    history[node] = False
    for child in l[node]:
        if history[child]:
            deg1[child] += 1
            deg2[child] += deg1[node]
            deg1[node] += 1
            stack.append(child)
            
print(ans)

Buggy python submission (verdict: Runtime Error):
N, K = list(map(int, input().split()))
links = [list(map(int, input().split())) for _ in range(N-1)]
start = links[0][0]

def perm(a, b):
    s = 1
    for i in range(a-b+1, a+1):
        s *= i
    return s

if N == 1:
    print(K)
elif K - 1 < len(d[start]):
    print(0)
else:
    mod = 1000000007
    d = {}
    for a, b in links:
        if a in d:
            d[a].append(b)
        else:
            d[a] = [b]
    ans = K * perm(K - 1, len(d[start]))
    root = d[start]
    a = K - 2
    while True:
        children = []
        for i in root:
            if i in d:
                b = len(d[i])
                if a < b:
                    print(0)
                    break
                ans *= perm(a, b)
                children.extend(d[i])
        else:
            if children == []:
                print(ans % mod)
                break
            root = children
            continue
        break

Fixed submission:
N, K = list(map(int, input().split()))
l = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    a, b = list(map(int, input().split()))
    l[a].append(b)
    l[b].append(a)

deg1 = [0] * (N + 1)
deg2 = [0] * (N + 1)
history = [True] * (N + 1)
stack = [1]
ans = 1

while stack:
    node = stack.pop()
    ans *= K - deg1[node] - deg2[node]
    ans %= 1000000007
    history[node] = False
    for child in l[node]:
        if history[child]:
            deg1[child] += 1
            deg2[child] += deg1[node]
            deg1[node] += 1
            stack.append(child)
            
print(ans)

Buggy python submission (verdict: Runtime Error):
N, K = list(map(int, input().split()))
links = [list(map(int, input().split())) for _ in range(N-1)]

def perm(a, b):
    s = 1
    for i in range(a-b+1, a+1):
        s *= i
    return s

if N == 1:
    print(K)
elif K - 1 < len(d[1]):
    print(0)
else:
    mod = 1000000007
    d = {}
    for a, b in links:
        if a in d:
            d[a].append(b)
        else:
            d[a] = [b]
    ans = K * perm(K - 1, len(d[1]))
    root = d[1]
    a = K - 2
    while True:
        children = []
        for i in root:
            if i in d:
                b = len(d[i])
                if a < b:
                    print(0)
                    break
                ans *= perm(a, b)
                children.extend(d[i])
        else:
            if children == []:
                print(ans % mod)
                break
            root = children
            continue
        break

Fixed submission:
N, K = list(map(int, input().split()))
l = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    a, b = list(map(int, input().split()))
    l[a].append(b)
    l[b].append(a)

deg1 = [0] * (N + 1)
deg2 = [0] * (N + 1)
history = [True] * (N + 1)
stack = [1]
ans = 1

while stack:
    node = stack.pop()
    ans *= K - deg1[node] - deg2[node]
    ans %= 1000000007
    history[node] = False
    for child in l[node]:
        if history[child]:
            deg1[child] += 1
            deg2[child] += deg1[node]
            deg1[node] += 1
            stack.append(child)
            
print(ans)

Buggy python submission (verdict: Runtime Error):
N, K = list(map(int, input().split()))
links = [list(map(int, input().split())) for _ in range(N-1)]

def perm(a, b):
    s = 1
    for i in range(a-b+1, a+1):
        s *= i
    return s

if N == 1:
    print(K)
elif K - 1 < d[1]:
    print(0)
else:
    mod = 1000000007
    d = {}
    for a, b in links:
        if a in d:
            d[a].append(b)
        else:
            d[a] = [b]
    ans = K * perm(K - 1, len(d[1]))
    root = d[1]
    a = K - 2
    while True:
        children = []
        for i in root:
            if i in d:
                b = len(d[i])
                if a < b:
                    print(0)
                    break
                ans *= perm(a, b)
                children.extend(d[i])
        else:
            if children == []:
                print(ans % mod)
                break
            root = children
            continue
        break

Fixed submission:
N, K = list(map(int, input().split()))
l = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    a, b = list(map(int, input().split()))
    l[a].append(b)
    l[b].append(a)

deg1 = [0] * (N + 1)
deg2 = [0] * (N + 1)
history = [True] * (N + 1)
stack = [1]
ans = 1

while stack:
    node = stack.pop()
    ans *= K - deg1[node] - deg2[node]
    ans %= 1000000007
    history[node] = False
    for child in l[node]:
        if history[child]:
            deg1[child] += 1
            deg2[child] += deg1[node]
            deg1[node] += 1
            stack.append(child)
            
print(ans)

Buggy python submission (verdict: Runtime Error):
N, K = list(map(int, input().split()))
links = [list(map(int, input().split())) for _ in range(N-1)]

def perm(a, b):
    s = 1
    for i in range(a-b+1, a+1):
        s *= i
    return s

if N == 1:
    print(K)
elif K == 1:
    print(0)
else:
    mod = 1000000007
    d = {}
    for a, b in links:
        if a in d:
            d[a].append(b)
        else:
            d[a] = [b]
    ans = K * perm(K - 1, len(d[1]))
    root = d[1]
    a = K - 2
    while True:
        children = []
        for i in root:
            if i in d:
                b = len(d[i])
                if a < b:
                    print(0)
                    break
                ans *= perm(a, b)
                children.extend(d[i])
        else:
            if children == []:
                print(ans % mod)
                break
            root = children
            continue
        break

Fixed submission:
N, K = list(map(int, input().split()))
l = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    a, b = list(map(int, input().split()))
    l[a].append(b)
    l[b].append(a)

deg1 = [0] * (N + 1)
deg2 = [0] * (N + 1)
history = [True] * (N + 1)
stack = [1]
ans = 1

while stack:
    node = stack.pop()
    ans *= K - deg1[node] - deg2[node]
    ans %= 1000000007
    history[node] = False
    for child in l[node]:
        if history[child]:
            deg1[child] += 1
            deg2[child] += deg1[node]
            deg1[node] += 1
            stack.append(child)
            
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N, K = list(map(int, input().split()))
links = [list(map(int, input().split())) for _ in range(N-1)]

def perm(a, b):
    s = 1
    for i in range(a-b+1, a+1):
        s *= i
    return s

if N == 1:
    print(K)
elif K == 1:
    print(0)
else:
    mod = 1000000007
    d = {}
    for a, b in links:
        if a in d:
            d[a].append(b)
        else:
            d[a] = [b]
        if b in d:
            d[b].append(a)
        else:
            d[b] = [a]
    for j in d[1]:
        d[j].remove(1)
    ans = K * perm(K - 1, len(d[1]))
    root = d[1]
    a = K - 2
    while True:
        children = []
        for i in root:
            for j in d[i]:
                d[j].remove(i)
            b = len(d[i])
            if a < b:
                print(0)
                break
            if b == 0:
                continue
            ans *= perm(a, b)
            children.extend(d[i])
        else:
            if children == []:
                print(ans % mod)
                break
            root = children
            continue
        break

Fixed submission:
N, K = list(map(int, input().split()))
l = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    a, b = list(map(int, input().split()))
    l[a].append(b)
    l[b].append(a)

deg1 = [0] * (N + 1)
deg2 = [0] * (N + 1)
history = [True] * (N + 1)
stack = [1]
ans = 1

while stack:
    node = stack.pop()
    ans *= K - deg1[node] - deg2[node]
    ans %= 1000000007
    history[node] = False
    for child in l[node]:
        if history[child]:
            deg1[child] += 1
            deg2[child] += deg1[node]
            deg1[node] += 1
            stack.append(child)
            
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N, K = list(map(int, input().split()))
links = [list(map(int, input().split())) for _ in range(N-1)]

def perm(a, b):
    s = 1
    for i in range(a-b+1, a+1):
        s *= i
    return s

if N == 1:
    print(K)
else:
    mod = 1000000007
    d = {}
    for a, b in links:
        if a in d:
            d[a].append(b)
        else:
            d[a] = [b]
        if b in d:
            d[b].append(a)
        else:
            d[b] = [a]
    root = [1]
    ans = K
    while True:
        a = K - 2
        if root[0] == 1:
            a = K - 1
        children = []
        for i in root:
            for j in d[i]:
                d[j].remove(i)
            b = len(d[i])
            if a < b:
                print(0)
                break
            if b == 0:
                continue
            ans *= perm(a, b)
            children.extend(d[i])
        else:
            if len(children) == 0:
                print(ans % mod)
                break
            root = children
            continue
        break

Fixed submission:
N, K = list(map(int, input().split()))
l = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    a, b = list(map(int, input().split()))
    l[a].append(b)
    l[b].append(a)

deg1 = [0] * (N + 1)
deg2 = [0] * (N + 1)
history = [True] * (N + 1)
stack = [1]
ans = 1

while stack:
    node = stack.pop()
    ans *= K - deg1[node] - deg2[node]
    ans %= 1000000007
    history[node] = False
    for child in l[node]:
        if history[child]:
            deg1[child] += 1
            deg2[child] += deg1[node]
            deg1[node] += 1
            stack.append(child)
            
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N, K = list(map(int, input().split()))
links = [list(map(int, input().split())) for _ in range(N-1)]

def perm(a, b):
    s = 1
    for i in range(a-b+1, a+1):
        s *= i
    return s

if N == 1:
    print(K)
else:
#     from scipy import special
    mod = 1000000007
    d = {}
    for a, b in links:
        if a in d:
            d[a].add(b)
        else:
            d[a] = {b}
        if b in d:
            d[b].add(a)
        else:
            d[b] = {a}
    root = {1}
    ans = K
    while True:
        a = K - 2
        if 1 in root:
            a = K - 1
        children = set()
        for i in root:
            for j in d[i]:
                d[j].remove(i)
            b = len(d[i])
            if a < b:
                print(0)
                break
            if b == 0:
                continue
            ans *= perm(a, b)
#             ans *= special.perm(a, b, exact=True)
            children |= d[i]
        else:
            if len(children) == 0:
                print(ans % mod)
                break
            root = children
            continue
        break

Fixed submission:
N, K = list(map(int, input().split()))
l = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    a, b = list(map(int, input().split()))
    l[a].append(b)
    l[b].append(a)

deg1 = [0] * (N + 1)
deg2 = [0] * (N + 1)
history = [True] * (N + 1)
stack = [1]
ans = 1

while stack:
    node = stack.pop()
    ans *= K - deg1[node] - deg2[node]
    ans %= 1000000007
    history[node] = False
    for child in l[node]:
        if history[child]:
            deg1[child] += 1
            deg2[child] += deg1[node]
            deg1[node] += 1
            stack.append(child)
            
print(ans)

Buggy python submission (verdict: Runtime Error):
from scipy import special
N, K = list(map(int, input().split()))
links = [list(map(int, input().split())) for _ in range(N-1)]

if N == 1:
    print(K)
else:
    mod = 1000000007
    d = {}
    for a, b in links:
        if a in d:
            d[a].add(b)
        else:
            d[a] = {b}
        if b in d:
            d[b].add(a)
        else:
            d[b] = {a}
    root = {1}
    ans = K
    while True:
        a = K - 2
        if 1 in root:
            a = K - 1
        children = set()
        for i in root:
            for j in d[i]:
                d[j].remove(i)
            b = len(d[i])
            if a < b:
                print(0)
                break
            if b == 0:
                continue
            ans *= special.perm(a, b, exact=True)
            children |= d[i]
        else:
            if len(children) == 0:
                print(ans % mod)
                break
            root = children
            continue
        break

Fixed submission:
N, K = list(map(int, input().split()))
l = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    a, b = list(map(int, input().split()))
    l[a].append(b)
    l[b].append(a)

deg1 = [0] * (N + 1)
deg2 = [0] * (N + 1)
history = [True] * (N + 1)
stack = [1]
ans = 1

while stack:
    node = stack.pop()
    ans *= K - deg1[node] - deg2[node]
    ans %= 1000000007
    history[node] = False
    for child in l[node]:
        if history[child]:
            deg1[child] += 1
            deg2[child] += deg1[node]
            deg1[node] += 1
            stack.append(child)
            
print(ans)

Buggy python submission (verdict: Runtime Error):
N, K = list(map(int, input().split()))
links = [list(map(int, input().split())) for _ in range(N-1)]

if N == 1:
    print(K)
else:
    from scipy import special
    mod = 1000000007
    d = {}
    for a, b in links:
        if a in d:
            d[a].add(b)
        else:
            d[a] = {b}
        if b in d:
            d[b].add(a)
        else:
            d[b] = {a}
    root = {1}
    ans = K
    while True:
        a = K - 2
        if 1 in root:
            a = K - 1
        children = set()
        for i in root:
            for j in d[i]:
                d[j].remove(i)
            b = len(d[i])
            if a < b:
                print(0)
                break
            if b == 0:
                continue
            ans *= special.perm(a, b, exact=True)
            children |= d[i]
        else:
            if len(children) == 0:
                print(ans % mod)
                break
            root = children
            continue
        break

Fixed submission:
N, K = list(map(int, input().split()))
l = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    a, b = list(map(int, input().split()))
    l[a].append(b)
    l[b].append(a)

deg1 = [0] * (N + 1)
deg2 = [0] * (N + 1)
history = [True] * (N + 1)
stack = [1]
ans = 1

while stack:
    node = stack.pop()
    ans *= K - deg1[node] - deg2[node]
    ans %= 1000000007
    history[node] = False
    for child in l[node]:
        if history[child]:
            deg1[child] += 1
            deg2[child] += deg1[node]
            deg1[node] += 1
            stack.append(child)
            
print(ans)

Buggy python submission (verdict: Runtime Error):
N, K = list(map(int, input().split()))
links = [list(map(int, input().split())) for _ in range(N-1)]

if N == 1:
    print(K)
else:
    from scipy import special
    mod = 1000000007
    d = {}
    for a, b in links:
        if a in d:
            d[a].add(b)
        else:
            d[a] = {b}
        if b in d:
            d[b].add(a)
        else:
            d[b] = {a}
    root = {1}
    ans = K
    while True:
        a = K - 2
        if 1 in root:
            a = K - 1
        children.clear()
        for i in root:
            for j in d[i]:
                d[j].remove(i)
            b = len(d[i])
            if a < b:
                print(0)
                break
            if b == 0:
                continue
            ans *= special.perm(a, b, exact=True)
            children |= d[i]
        else:
            if len(children) == 0:
                print(ans % mod)
                break
            root = children
            continue
        break

Fixed submission:
N, K = list(map(int, input().split()))
l = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    a, b = list(map(int, input().split()))
    l[a].append(b)
    l[b].append(a)

deg1 = [0] * (N + 1)
deg2 = [0] * (N + 1)
history = [True] * (N + 1)
stack = [1]
ans = 1

while stack:
    node = stack.pop()
    ans *= K - deg1[node] - deg2[node]
    ans %= 1000000007
    history[node] = False
    for child in l[node]:
        if history[child]:
            deg1[child] += 1
            deg2[child] += deg1[node]
            deg1[node] += 1
            stack.append(child)
            
print(ans)

Buggy python submission (verdict: Runtime Error):
N, K = list(map(int, input().split()))
links = [list(map(int, input().split())) for _ in range(N-1)]

if N == 1:
    print(K)
else:
    from scipy import special
    mod = 1000000007
    d = {}
    for a, b in links:
        if a in d:
            d[a].add(b)
        else:
            d[a] = {b}
        if b in d:
            d[b].add(a)
        else:
            d[b] = {a}
    root = {1}
    ans = K
    while True:
        a = K - 2
        if 1 in root:
            a = K - 1
        children = set()
        for i in root:
            for j in d[i]:
                d[j].remove(i)
            b = len(d[i])
            if a < b:
                print(0)
                break
            if b == 0:
                continue
            ans *= special.perm(a, b, exact=True)
            children |= d[i]
        else:
            if len(children) == 0:
                print(ans % mod)
                break
            root = children
            continue
        break

Fixed submission:
N, K = list(map(int, input().split()))
l = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    a, b = list(map(int, input().split()))
    l[a].append(b)
    l[b].append(a)

deg1 = [0] * (N + 1)
deg2 = [0] * (N + 1)
history = [True] * (N + 1)
stack = [1]
ans = 1

while stack:
    node = stack.pop()
    ans *= K - deg1[node] - deg2[node]
    ans %= 1000000007
    history[node] = False
    for child in l[node]:
        if history[child]:
            deg1[child] += 1
            deg2[child] += deg1[node]
            deg1[node] += 1
            stack.append(child)
            
print(ans)

Buggy python submission (verdict: Runtime Error):
N, K = list(map(int, input().split()))
links = [list(map(int, input().split())) for _ in range(N-1)]

if N == 1:
    print(K)
else:
    from scipy import special
    mod = 1000000007

    d = {}
    for a, b in links:
        if a in d:
            d[a].add(b)
        else:
            d[a] = {b}
        if b in d:
            d[b].add(a)
        else:
            d[b] = {a}
    root = {1}
    ans = K
    while True:
        a = K - 2
        if 1 in root:
            a = K - 1
        children = set()
        for i in root:
            for j in d[i]:
                d[j].remove(i)
            b = len(d[i])
            if a < b:
                print(0)
                break
            if b == 0:
                continue
            ans *= special.perm(a, b, exact=True)
            children |= d[i]
        else:
            if len(children) == 0:
                print(ans % mod)
                break
            root = children
            continue
        break

Fixed submission:
N, K = list(map(int, input().split()))
l = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    a, b = list(map(int, input().split()))
    l[a].append(b)
    l[b].append(a)

deg1 = [0] * (N + 1)
deg2 = [0] * (N + 1)
history = [True] * (N + 1)
stack = [1]
ans = 1

while stack:
    node = stack.pop()
    ans *= K - deg1[node] - deg2[node]
    ans %= 1000000007
    history[node] = False
    for child in l[node]:
        if history[child]:
            deg1[child] += 1
            deg2[child] += deg1[node]
            deg1[node] += 1
            stack.append(child)
            
print(ans)

Buggy python submission (verdict: Runtime Error):
from scipy import special
N, K = list(map(int, input().split()))
links = [list(map(int, input().split())) for _ in range(N-1)]

mod = 1000000007

d = {}
for a, b in links:
    if a in d:
        d[a].add(b)
    else:
        d[a] = {b}
    if b in d:
        d[b].add(a)
    else:
        d[b] = {a}

if N == 1:
    print(K)
else:
    root = {1}
    ans = K
    while True:
        a = K - 2
        if 1 in root:
            a = K - 1
        children = set()
        for i in root:
            for j in d[i]:
                d[j].remove(i)
            b = len(d[i])
            if a < b:
                print(0)
                break
            ans *= special.perm(a, b, exact=True)
            children |= d[i]
        else:
            if len(children) == 0:
                print(ans % mod)
                break
            root = children
            continue
        break

Fixed submission:
N, K = list(map(int, input().split()))
l = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    a, b = list(map(int, input().split()))
    l[a].append(b)
    l[b].append(a)

deg1 = [0] * (N + 1)
deg2 = [0] * (N + 1)
history = [True] * (N + 1)
stack = [1]
ans = 1

while stack:
    node = stack.pop()
    ans *= K - deg1[node] - deg2[node]
    ans %= 1000000007
    history[node] = False
    for child in l[node]:
        if history[child]:
            deg1[child] += 1
            deg2[child] += deg1[node]
            deg1[node] += 1
            stack.append(child)
            
print(ans)

Buggy python submission (verdict: Runtime Error):
N, K = list(map(int, input().split()))
links = [list(map(int, input().split())) for _ in range(N-1)]

mod = 1000000007

from scipy import special

d = {}
for a, b in links:
    if a in d:
        d[a].add(b)
    else:
        d[a] = {b}
    if b in d:
        d[b].add(a)
    else:
        d[b] = {a}

root = {1}
ans = K
while True:
    a = K - 2
    if 1 in root:
        a = K - 1
    children = set()
    for i in root:
        for j in d[i]:
            d[j].remove(i)
        b = len(d[i])
        if a < b:
            ans = 0
            break
        ans *= special.perm(a, b, exact=True)
        children |= d[i]
    else:
        if len(children) == 0:
            print(ans % mod)
            break
        root = children
        continue
    print(ans)
    break

Fixed submission:
N, K = list(map(int, input().split()))
l = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    a, b = list(map(int, input().split()))
    l[a].append(b)
    l[b].append(a)

deg1 = [0] * (N + 1)
deg2 = [0] * (N + 1)
history = [True] * (N + 1)
stack = [1]
ans = 1

while stack:
    node = stack.pop()
    ans *= K - deg1[node] - deg2[node]
    ans %= 1000000007
    history[node] = False
    for child in l[node]:
        if history[child]:
            deg1[child] += 1
            deg2[child] += deg1[node]
            deg1[node] += 1
            stack.append(child)
            
print(ans)

Buggy python submission (verdict: Runtime Error):
N, K = list(map(int, input().split()))
links = [list(map(int, input().split())) for _ in range(N-1)]

mod = 1000000007

from scipy import special

d = {}
for a, b in links:
    if a in d:
        d[a].add(b)
    else:
        d[a] = {b}
    if b in d:
        d[b].add(a)
    else:
        d[b] = {a}

root = {1}
ans = K
while True:
    a = K - 2
    if 1 in root:
        a = K - 1
    children = set()
    for i in root:
        for j in d[i]:
            d[j].remove(i)
        b = len(d[i])
        if a < b:
            print(0)
            break
        ans *= special.perm(a, b, exact=True)
        children |= d[i]
    else:
        if len(children) == 0:
            print(ans % mod)
            break
        root = children
        continue
    break

Fixed submission:
N, K = list(map(int, input().split()))
l = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    a, b = list(map(int, input().split()))
    l[a].append(b)
    l[b].append(a)

deg1 = [0] * (N + 1)
deg2 = [0] * (N + 1)
history = [True] * (N + 1)
stack = [1]
ans = 1

while stack:
    node = stack.pop()
    ans *= K - deg1[node] - deg2[node]
    ans %= 1000000007
    history[node] = False
    for child in l[node]:
        if history[child]:
            deg1[child] += 1
            deg2[child] += deg1[node]
            deg1[node] += 1
            stack.append(child)
            
print(ans)

Buggy python submission (verdict: Runtime Error):
N, K = list(map(int, input().split()))
links = [list(map(int, input().split())) for _ in range(N-1)]

mod = 1000000007

from scipy import special

d = {}
for a, b in links:
    if a in d:
        d[a].add(b)
    else:
        d[a] = {b}
    if b in d:
        d[b].add(a)
    else:
        d[b] = {a}

root = {1}
ans = K
while True:
    a = K - 2
    if 1 in root:
        a = K - 1
    children = set()
    for i in root:
        for j in d[i]:
            d[j].remove(i)
        b = len(d[i])
        if a < b:
            print(0)
            break
        ans *= special.perm(a, b, exact=True)
        children |= d[i]
    else:
        if len(children) == 0:
            print(ans % mod)
            break
        root = children
        continue
    break

Fixed submission:
N, K = list(map(int, input().split()))
l = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    a, b = list(map(int, input().split()))
    l[a].append(b)
    l[b].append(a)

deg1 = [0] * (N + 1)
deg2 = [0] * (N + 1)
history = [True] * (N + 1)
stack = [1]
ans = 1

while stack:
    node = stack.pop()
    ans *= K - deg1[node] - deg2[node]
    ans %= 1000000007
    history[node] = False
    for child in l[node]:
        if history[child]:
            deg1[child] += 1
            deg2[child] += deg1[node]
            deg1[node] += 1
            stack.append(child)
            
print(ans)