Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.readline
mod = 10**9+7
def dfs(n,fr):
    color = 0
    if(fr==-1):
        color = K-1
    else:
        color = K-2
    if(K<len(edges[n])):
        return 0
    else:
        case_num = 1
        for e in edges[n]:
            if(e==fr):continue
            case_num*=color
            color-=1
        for e in edges[n]:
            if(e==fr):continue
            case_num*=dfs(e,n)
        return case_num%mod

if(__name__=='__main__'):
    N,K = [int(x) for x in input().split()]
    edges = [[] for _ in range(N)]
    for _ in range(N-1):
        s,d = [int(x) for x in input().split()]
        edges[s-1].append(d-1)
        edges[d-1].append(s-1)
    ans = K*dfs(0,-1)
    print(ans%mod)


Fixed submission:
import sys
from collections import deque
sys.setrecursionlimit(1000000)
input = sys.stdin.readline
mod = 10**9+7
def dfs():
    stack = deque([[-1,0]])
    visited = set()
    case_num=1
    while stack:
        fr,n = stack.pop()
        if(n in visited):continue
        visited.add(n)
        color = 0
        if(fr==-1):
            color = K-1
        else:
            color = K-2
        if(K<len(edges[n])):
            return 0
        else:
            for e in edges[n]:
                if(e==fr):continue
                case_num*=color
                color-=1
                stack.append([n,e])
                case_num%=mod
    return case_num%mod

if(__name__=='__main__'):
    N,K = [int(x) for x in input().split()]
    edges = [[] for _ in range(N)]
    for _ in range(N-1):
        s,d = [int(x) for x in input().split()]
        edges[s-1].append(d-1)
        edges[d-1].append(s-1)
    ans = K*dfs()
    print(ans%mod)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.readline
mod = 10**9+7
def dfs(n,fr):
    color = 0
    if(fr==-1):
        color = K-1
    else:
        color = K-2
    if(K<len(edges[n])):
        return 0
    else:
        case_num = 1
        for e in edges[n]:
            if(e==fr):continue
            case_num*=color
            case_num*=dfs(e,n)
            color-=1
            case_num%=mod

        return case_num

if(__name__=='__main__'):
    N,K = [int(x) for x in input().split()]
    edges = [[] for _ in range(N)]
    for _ in range(N-1):
        s,d = [int(x) for x in input().split()]
        edges[s-1].append(d-1)
        edges[d-1].append(s-1)
    ans = K*dfs(0,-1)
    print(ans%mod)


Fixed submission:
import sys
from collections import deque
sys.setrecursionlimit(1000000)
input = sys.stdin.readline
mod = 10**9+7
def dfs():
    stack = deque([[-1,0]])
    visited = set()
    case_num=1
    while stack:
        fr,n = stack.pop()
        if(n in visited):continue
        visited.add(n)
        color = 0
        if(fr==-1):
            color = K-1
        else:
            color = K-2
        if(K<len(edges[n])):
            return 0
        else:
            for e in edges[n]:
                if(e==fr):continue
                case_num*=color
                color-=1
                stack.append([n,e])
                case_num%=mod
    return case_num%mod

if(__name__=='__main__'):
    N,K = [int(x) for x in input().split()]
    edges = [[] for _ in range(N)]
    for _ in range(N-1):
        s,d = [int(x) for x in input().split()]
        edges[s-1].append(d-1)
        edges[d-1].append(s-1)
    ans = K*dfs()
    print(ans%mod)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.readline
N,K = [int(x) for x in input().split()]
edge = [[int(x) for x in input().split()]for _ in range(N-1)]
mod = 10**9+7
def dfs(n,fr):
    color = 0
    if(fr==-1):
        color = K-1
    else:
        color = K-2
    if(K<len(edges[n])):
        return 0
    else:
        case_num = 1
        for e in edges[n]:
            if(e==fr):continue
            case_num*=color
            case_num*=dfs(e,n)
            color-=1
            case_num%=mod
            
        return case_num

edges = [[] for _ in range(N)]
for s,d in edge:
    s-=1
    d-=1
    edges[s].append(d)
    edges[d].append(s)
ans = K*dfs(0,-1)
print(ans%mod)


Fixed submission:
import sys
from collections import deque
sys.setrecursionlimit(1000000)
input = sys.stdin.readline
mod = 10**9+7
def dfs():
    stack = deque([[-1,0]])
    visited = set()
    case_num=1
    while stack:
        fr,n = stack.pop()
        if(n in visited):continue
        visited.add(n)
        color = 0
        if(fr==-1):
            color = K-1
        else:
            color = K-2
        if(K<len(edges[n])):
            return 0
        else:
            for e in edges[n]:
                if(e==fr):continue
                case_num*=color
                color-=1
                stack.append([n,e])
                case_num%=mod
    return case_num%mod

if(__name__=='__main__'):
    N,K = [int(x) for x in input().split()]
    edges = [[] for _ in range(N)]
    for _ in range(N-1):
        s,d = [int(x) for x in input().split()]
        edges[s-1].append(d-1)
        edges[d-1].append(s-1)
    ans = K*dfs()
    print(ans%mod)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(1000000)
N,K = [int(x) for x in input().split()]
edge = [[int(x) for x in input().split()]for _ in range(N-1)]
mod = 10**9+7
def dfs(n,fr):
    color = 0
    if(fr==-1):
        color = K-1
    else:
        color = K-2
    if(K<len(edges[n])):
        return 0
    else:
        case_num = 1
        for e in edges[n]:
            if(e==fr):continue
            case_num*=color
            color-=1
            case_num%=mod

        for e in edges[n]:
            if(e==fr):continue
            case_num*=dfs(e,n)
            case_num%=mod
        return case_num

edges = [[] for _ in range(N)]
for s,d in edge:
    s-=1
    d-=1
    edges[s].append(d)
    edges[d].append(s)
ans = K*dfs(0,-1)
print(ans%mod)


Fixed submission:
import sys
from collections import deque
sys.setrecursionlimit(1000000)
input = sys.stdin.readline
mod = 10**9+7
def dfs():
    stack = deque([[-1,0]])
    visited = set()
    case_num=1
    while stack:
        fr,n = stack.pop()
        if(n in visited):continue
        visited.add(n)
        color = 0
        if(fr==-1):
            color = K-1
        else:
            color = K-2
        if(K<len(edges[n])):
            return 0
        else:
            for e in edges[n]:
                if(e==fr):continue
                case_num*=color
                color-=1
                stack.append([n,e])
                case_num%=mod
    return case_num%mod

if(__name__=='__main__'):
    N,K = [int(x) for x in input().split()]
    edges = [[] for _ in range(N)]
    for _ in range(N-1):
        s,d = [int(x) for x in input().split()]
        edges[s-1].append(d-1)
        edges[d-1].append(s-1)
    ans = K*dfs()
    print(ans%mod)