You are given a tree with N vertices and N-1 edges. The vertices are numbered 1 to N, and the i-th edge connects Vertex a_i and b_i.
You have coloring materials of K colors.
For each vertex in the tree, you will choose one of the K colors to paint it, so that the following condition is satisfied:
 - If the distance between two different vertices x and y is less than or equal to two, x and y have different colors.
How many ways are there to paint the tree? Find the count modulo 1\ 000\ 000\ 007.
What is tree?
A tree is a kind of graph. For detail, please see: Wikipedia "Tree (graph theory)"

What is distance?
The distance between two vertices x and y is the minimum number of edges one has to traverse to get from x to y.

-----Constraints-----
 - 1 \leq N,K \leq 10^5
 - 1 \leq a_i,b_i \leq N
 - The given graph is a tree.

-----Input-----
Input is given from Standard Input in the following format:
N K
a_1 b_1
a_2 b_2
.
.
.
a_{N-1} b_{N-1}

-----Output-----
Print the number of ways to paint the tree, modulo 1\ 000\ 000\ 007.

-----Sample Input-----
4 3
1 2
2 3
3 4

-----Sample Output-----
6


There are six ways to paint the tree.

Difficulty: interview

Starter code:

Solutions:
import sys
sys.setrecursionlimit(4100000)

mod = 10 ** 9 + 7

N, K = map(int,input().split())
graph = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int,input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

ans = K

def factorial(n, k, mod):
    fact = 1
    for integer in range(n, n-k, -1):
        fact *= integer
        fact %= mod
    return fact

def dfs(parent, current):
    ret = 1
    for child in graph[current]:
        if child != parent:
            ret *= dfs(current, child)
    L = len(graph[current])
    R = K - 1
    if parent != -1:
        L -= 1
        R -= 1
    ret *= factorial(R, L, mod)
    return ret % mod

ans *= dfs(-1, 0)
ans %= mod

print(ans)

import sys
from collections import deque
def input(): return sys.stdin.readline().rstrip()

def per(n, r, mod=10**9+7):  # 順列数
    per = 1
    for i in range(r):
        per = per*(n-i) % mod
    return per
 
n, k = map(int, input().split())
mod=10**9+7
graph = [[] for _ in range(n+1)]

for i in range(n-1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

dist = [-1] * (n+1)
dist[0] = 0
dist[1] = 0

d = deque()
d.append(1)
ans=k
while d:
    v = d.popleft()
    cnt=0
    for i in graph[v]:
        if dist[i] != -1:
            continue
        dist[i] = dist[v] + 1
        d.append(i)
        cnt+=1
    if cnt>0:
        if v==1:
            ans=ans*per(k-1,cnt)%mod
        else:
            ans=ans*per(k-2,cnt)%mod
    


print(ans)

from collections import deque, Counter

N,K,*abf = map(int, open(0).read().split())
ab = [abf[i:i+2] for i in range(0, len(abf), 2)]
connected = [[] for _ in range(N+1)]
m = 1000000007
for a, b in ab:
    connected[a].append(b)
    connected[b].append(a)
    
dist = [-1] * (N+1)
d = deque([1])
parents = [-1] * (N+1)
dist[1] = 0
while d:
    temp = d.popleft()
    for edge in connected[temp]:
        if dist[edge] == -1:
            d.append(edge)
            dist[edge] = dist[temp] + 1
            parents[edge] = temp
ans = K
c = Counter(parents)
for x in c.items():
    if x[0] < 1:
        continue
    elif x[0] == 1:
        for i in range(1,x[1]+1):
            ans = (ans*(K-i)) % m
    else:
        for i in range(2,x[1]+2):
            ans = (ans*(K-i)) % m
print(ans)

import sys
sys.setrecursionlimit(10**9)

MOD = 10**9 + 7
n, k = list(map(int, input().split()))
graph = [[] for _ in range(n)]
k_inv = pow(k, MOD - 2, MOD)
for _ in range(n - 1):
    a, b = list(map(int, input().split()))
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)


def dfs(v, v_p):
    # 子部分木の塗り方の場合の数
    if v_p == -1:  # root
        c = k - 1
    else:
        c = k - 2

    cnt = 1
    i = 0
    for v_next in graph[v]:
        if v_next == v_p:
            continue
        cnt *= max(0, c - i)
        cnt %= MOD
        cnt *= dfs(v_next, v)
        cnt %= MOD
        i += 1
    return cnt


ans = dfs(0, -1) * k % MOD
print(ans)


N, K = map(int, input().split())
mod = 1000000007

E = [[] for i in range(N)]
for i in range(N-1):
  a, b = map(int, input().split())
  E[a-1].append(b-1)
  E[b-1].append(a-1)
#ここまでで木をリスト化

counts = [False]*N
#各々の頂点について1回ずつ考えるようにTrueになったら進行しないようにコマンド
q = [0]
counts[0] = True
ans = K
while q:
  i = q.pop(0)
  # get_nexts
  js = E[i]
  if i == 0:
    c = K - 1
  else:
    c = K - 2
  for j in js:
    if not(counts[j]):
      counts[j] = True
      ans = (ans * c) % mod
      c -= 1
      q.append(j)
#print(E)      
print(ans)

import networkx as nx

int1 = lambda x: int(x) - 1
MOD = 10 ** 9 + 7

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

G = nx.Graph()
G.add_nodes_from(list(range(N)))
G.add_edges_from([tuple(map(int1, input().split())) for _ in range(N - 1)])

deg = nx.degree(G)
ans = K
for i in range(deg[0]):
    ans = (ans * (K - i - 1)) % MOD

for parent, child in nx.dfs_edges(G, 0):
    for i in range(deg[child] - 1):
        ans = (ans * (K - i - 2)) % MOD

print(ans)


import sys
from collections import deque
MOD = 10 ** 9 + 7

n, k, *ab = map(int, sys.stdin.read().split())
graph = [[] for _ in range(n)]
for a, b in zip(*[iter(ab)] * 2):
  a -= 1; b -= 1
  graph[a].append(b)
  graph[b].append(a)

def main():
  for i in range(n):
    if len(graph[i]) + 1 > k:
      print(0)
      return
  
  cnt = [None] * n; cnt[0] = k
  parent = [None] * n
  stack = [0]
  while stack:
    u = stack.pop()
    c = k - 2 if not parent[u] is None else k - 1
    for v in graph[u]:
      if v == parent[u]: continue 
      parent[v] = u
      cnt[v] = c
      c -= 1
      stack.append(v)

  res = 1
  for c in cnt:
    res *= c
    res %= MOD
  print(res)

def __starting_point():
  main()
__starting_point()


N,K = map(int, input().split())
MOD = 10**9 + 7
es = [[] for _ in range(N)]
for _ in range(N-1):
    a,b = map(int, input().split())
    es[a-1].append(b-1)
    es[b-1].append(a-1)


MAXN = K+5
fac = [1,1] + [0]*MAXN
finv = [1,1] + [0]*MAXN
inv = [0,1] + [0]*MAXN
for i in range(2,MAXN+2):
    fac[i] = fac[i-1] * i % MOD
    inv[i] = -inv[MOD%i] * (MOD // i) % MOD
    finv[i] = finv[i-1] * inv[i] % MOD
 
def nPr(n,r):
    if n < r:
        return 0
    return fac[n] * finv[n-r]
"""
curr とその親prevの色が決まっているときに、currの子nxtの色の塗り方の場合の数は
nPr(K-2, len(es[curr]) - 1)
Kのうちprevとcurrで２色使っていて、currにつながっているもののうち一つはprevだから、１引いたものが子供の数。
で、一番初めのノードoriginについて考えると、親はないのでノードorigin自体はK個の塗り方があり、その子には、nPr(K-1, len(es[origin]))の塗り方がある
あとはDFS的に子供の塗り方を決めていく

"""

checked = [False] * N
ans = K * nPr(K-1, len(es[0]))
checked[0] = True

stack = []
for nxt in es[0]:
    stack.append(nxt)

while stack:
    curr = stack.pop()
    checked[curr] = True
    ans *= nPr(K-2, len(es[curr]) - 1)
    if ans >= MOD: ans %= MOD
    for nxt in es[curr]:
        if not checked[nxt]:
            stack.append(nxt)

print(ans % MOD)

from collections import deque


class ModCalc:
    mod = 10**9 + 7

    def __init__(self, n):
        self.n = n
        self.inv = [1] * (self.n + 1)
        self.fac = [1] * (self.n + 1)
        self.finv = [1] * (self.n + 1)
        self.inv[0] = 0
        self.inv_table()

    def inv_table(self):
        for i in range(2, self.n+1):
            self.inv[i] = self.inv[self.mod % i] * (self.mod - self.mod // i) % self.mod
            self.fac[i] = self.fac[i-1] * i % self.mod
            self.finv[i] = self.finv[i-1] * self.inv[i] % self.mod

    def comb(self, n, r):
        if n < r:
            return 0
        if n < 0 or r < 0:
            return 0

        return self.fac[n] * self.finv[r] % self.mod * self.finv[n-r] % self.mod

    def perm(self, n, r):
        if n < r:
            return 0
        if n < 0 or r < 0:
            return 0

        return self.fac[n] * self.finv[n-r] % self.mod

    def fact(self, n):
        return self.fac[n]


n, k = map(int, input().split())
tree = [[] for _ in range(n+1)]

for _ in range(n-1):
    a, b = map(int, input().split())
    tree[a].append(b)
    tree[b].append(a)

ans = k
mod = 10**9 + 7
mc = ModCalc(100001)

q = deque([1])
dist = [-1] * (n+1)
dist[1] = 0
while q:
    now = q.popleft()
    cnt = 0
    for node in tree[now]:
        if dist[node] != -1:
            continue
        cnt += 1
        q.append(node)
        dist[node] = dist[now] + 1

    if dist[now] == 0:
        ans *= mc.comb(k-1, cnt) * mc.fact(cnt) % mod
        ans %= mod
    else:
        ans *= mc.comb(k-2, cnt) * mc.fact(cnt) % mod
        ans %= mod

print(ans)

import sys 
sys.setrecursionlimit(10**6)
n, k = map(int, input().split())
edges = [[] for i in range(n)]
for i in range(n-1):
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    edges[a].append(b)
    edges[b].append(a)
    
mod = 10**9 + 7
def P(x,y):
    # x = k - 2
    # y = n - 1
    cnt = 0
    ans = 1
    waru = 1
    while cnt < y:
        ans *= (x-cnt)
        ans %= mod
        cnt += 1
    return ans%mod


ans = 1
def dfs(v,p):
    nonlocal ans
    us = edges[v]
    for u in us:
        if u == p: continue
        if len(edges[u]) == 1: ans *= 1
        ans *= P(k-2, len(edges[u])-1)   
        ans %= mod
        dfs(u,v)

dfs(0,-1)
n0 = len(edges[0])
a = P(k,n0+1)
# print(n0,a)
ans *= a
ans %= mod
print(ans)

import sys
sys.setrecursionlimit(200000)

mod = 10**9 +7
N,K = map(int,input().split())
edges = [[] for _ in range(N+1)]
for _ in range(N-1):
    a,b = map(int,input().split())
    edges[a].append(b)
    edges[b].append(a)


def dfs(cur,p,nei):
    #curにいる状態で、選べる色がcandi通りある場合の、塗り方の場合の数。
    #pが親,neiがcurの距離2以下のノードの数（curの子、弟ノードは除く）。neiが0,1のとき子に渡すneiはnei+1+兄の数、
    # neiが2のとき、子に渡すneiは、2+兄の数。
    res = K-nei 
    nxnei = min(nei+1,2)
    for nx in edges[cur]:
        if nx != p:
            res = res * dfs(nx,cur,nxnei) % mod
            nxnei += 1
    return res

print(dfs(1,0,0))

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return list(map(int, input().split()))
def S_MAP(): return list(map(str, input().split()))
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, K = MAP()
L = [LIST() for i in range(N-1)]
color = [0] * N
# color[]
graph = defaultdict(list)
for a, b in L:
    graph[a].append(b)
    graph[b].append(a)

ans = 1
# child, parent, kakerumono
q = deque([[1, 0, K]])
# color[0] = K
# visited = [False] * N
# visited[0] = True
while q:
    u, p, k_ = q.popleft()
    ans = (ans * k_) % mod
    if p == 0:
        # parentなし
        k_next = K - 1
    else:
        k_next = K - 2

    for v in graph[u]:
        if v == p:
            # 親と同じなら飛ばす
            continue
        q.append([v, u, k_next])
        # 子の数だけk_nextを減らしながら書けていく
        # K-2 P c_k
        k_next -= 1
print(ans)




n, k = list(map(int, input().split()))
ab = [list(map(int, input().split())) for _ in range(n - 1)]
mod = 10 ** 9 + 7

adj = [[] for _ in range(n + 1)]
for a, b in ab:
    adj[a].append(b)
    adj[b].append(a)

s = 1
p = [-1] * (n + 1)
p[0] = 0
p[1] = 0
c = [[] for _ in range(n + 1)]
order = []
stack = [s]
while stack:
    u = stack.pop()
    order.append(u)
    for v in adj[u]:
        if p[v] == -1:
            p[v] = u
            c[u].append(v)
            stack.append(v)

ans = k
for u in order:
    mx = k - 1
    par = p[u]
    if par:
        mx -= 1

    for i in range(len(c[u])):
        ans *= mx - i
        ans %= mod

print(ans)


#!/usr/bin/env python3

from functools import lru_cache

MOD = 10 ** 9 + 7

def main():
    n, k = list(map(int, input().split()))
    adj = [[] for i in range(n)]
    for i in range(n - 1):
        a, b = list(map(int, input().split()))
        a -= 1
        b -= 1
        adj[a].append(b)
        adj[b].append(a)
    res = k
    stack = [0]
    visited = [False for i in range(n)]
    while stack:
        i = stack.pop()
        visited[i] = True
        children = [x for x in adj[i] if not visited[x]]
        res *= perm((k - 1 if i == 0 else k - 2), len(children))
        res %= MOD
        for c in children:
            stack.append(c)
    print(res)

@lru_cache(maxsize=10 ** 6)
def perm(t, s):
    if s > t:
        return 0
    res = 1
    for i in range(s):
        res *= t
        res %= MOD
        t -= 1
    return res

def __starting_point():
    main()

__starting_point()

n, k = list(map(int, input().split()))
mod = 10**9+7
data = [[] for j in range(n+1)]
done = [0]*(n+1)
colors = [k-1]*(n+1)

for i in range(n-1):
  a, b = list(map(int, input().split()))
  data[min(a,b)].append(max(a,b))
  data[max(a,b)].append(min(a,b))

queue = [1]
ans = 1
colors[1] += 1
for d in data[1]:
  colors[d] += 1
while queue != []:
  idx = queue.pop(0)
  done[idx] = 1
  ans *= colors[idx]
  ans %= mod
  cnt = 0
  for i in range(len(data[idx])):
    if done[data[idx][i]]:
      continue
    cnt += 1
    colors[data[idx][i]] -= cnt
    queue.append(data[idx][i])

print(ans)
  


# https://atcoder.jp/contests/abc133/tasks/abc133_e

# あー解説あたまいい
# そのノードで塗れる色の候補を持つのではなくて、
# そのノードの子で塗れる通りの数を持っておく
# あるノードの子で塗れる通りの数は、親とそのノードで塗る色の通りも確定してると考えると、(K-2)P(子の数)となる。(自身が根のときは自身の色の通りも考慮して、(K)P(子の数+1)となる)
# これをdfsで実装すれば良い

import sys
from collections import defaultdict

sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def mina(*argv, sub=1): return list([x - sub for x in argv])
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def read_a_int(): return int(read())


def read_ints(): return list(map(int, read().split()))


MOD = 10**9 + 7

N, K = read_ints()
tree = defaultdict(lambda: [])
for _ in range(N - 1):
    a, b = read_ints()
    a, b = mina(a, b)
    tree[a].append(b)
    tree[b].append(a)


def perm_mod(n, r, mod=MOD):
    if n < r:  # そんな通りはありえない
        return 0

    ret = 1
    for _ in range(r):
        ret *= n
        ret %= mod
        n -= 1
    return ret


def dfs(u, p):  # 現在のuと親のp
    if len(tree[u]) == 1 and tree[u][0] == p:
        # 葉なので終了
        return 1
    ret = 1  # その地点までの通りの数
    for to in tree[u]:
        if to == p:
            continue
        ret *= dfs(to, u)
        ret %= MOD
    if p == -1:
        ret *= perm_mod(K, len(tree[u]) + 1)
    else:
        ret *= perm_mod(K - 2, len(tree[u]) - 1)

    return ret % MOD


print((dfs(0, -1)))


import sys
sys.setrecursionlimit(100000)
 

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

tree = [[] for _ in range(N+10)]

for i in range(N-1):
    a,b = list(map(int,input().split()))
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)

ans = []
def wfs(now,back):
    if now != 0:
        cnt = K - 2 #まず一個上のを引く。
    else:
        cnt = K - 1
    for nxt in tree[now]:
        if nxt != back:
            ans.append(cnt)
            cnt = cnt - 1
            wfs(nxt,now)

ans.append(K)
wfs(0,-1)

ans2 = 1
for j in range(len(ans)):
    ans2 = (ans2 * ans[j]) % (10**9+7)
print(ans2)

import sys
sys.setrecursionlimit(100000)

N,K=list(map(int,input().split()))
MOD=10**9+7
branch=[[] for _ in range(N)]
for i in range(N-1):
  a,b=list(map(int,input().split()))
  branch[a-1].append(b-1)
  branch[b-1].append(a-1)

if K==1:
  if N==1:
    print((1))
  else:
    print((0))
  return
  
P=[0]*(K-1)
P[K-2]=K-2
for i in range(K-3,0,-1):
  P[i]=P[i+1]*i%MOD
  
def PPP(start,num):
  if start<num:
    return 0
  if start==K-2:
    return P[start-num+1]
  if start==K-1:
    return P[start-num+2]*(K-1)%MOD
  
ans=1

def draw(parent,nord):
  nonlocal ans
  children=len(branch[nord])-(parent !=-1)
  if children==0:
    return
  #(K-2)*(K-1)*... をchildrenの数だけ掛ける。
  ans=ans*PPP(K-1-(parent !=-1),children)%MOD
  for b in branch[nord]:
    if b != parent:
      draw(nord,b)

for i in range(len(branch[0])+1):
  ans=ans*(K-i)%MOD
for bra in branch[0]:
  draw(0,bra)
print(ans)


import sys
sys.setrecursionlimit(10 ** 6)
N,K=map(int,input().split())
tree=[[]for _ in range(N+1)]
MOD=10**9+7
ans=K
enuk=[1]*(N)
for i in range(N-1):
    a,b=map(int,input().split())
    tree[a].append(b)
    tree[b].append(a)
    enuk[i+1]=(enuk[i]*(K-2-i))%MOD
def dfs(a,b):
    if a==1:
        node=len(tree[a])
        ret=1
        for i in range(node):
            ret*=K-1-i
            ret%=MOD
    else:
        node=len(tree[a])-1
        ret=enuk[node]%MOD
    for i in tree[a]:
        if i==b:
            continue
        ret=ret*dfs(i,a)%MOD
    return ret
ans*=dfs(1,0)
print(ans%MOD)

import sys
import re
import math
import collections
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal
import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: list(map(int, sys.stdin.readline().split()))
na = lambda: list(map(int, sys.stdin.readline().split()))
nb = lambda: list([int(x) - 1 for x in sys.stdin.readline().split()])


# ===CODE===


def main():
    n, k = ns()
    e = [[] for _ in range(n)]
    for _ in range(n - 1):
        a, b = ns()
        a, b = a - 1, b - 1
        e[a].append(b)
        e[b].append(a)

    table = [True for _ in range(n)]
    perm = [1]
    for i in range(k - 2, -1, -1):
        perm.append(perm[-1] * i % MOD)

    table[0] = False
    que = collections.deque(e[0])
    ans = k
    for i in range(len(e[0])):
        table[e[0][i]] = False
        ans *= k - i - 1
        ans %= MOD

    while len(que) > 0:
        for _ in range(len(que)):
            q = que.popleft()
            cnt = 0
            for i in range(len(e[q])):
                tmp = e[q][i]
                if table[tmp]:
                    table[tmp] = False
                    cnt += 1
                    que.appendleft(tmp)
            ans *= perm[min(len(perm) - 1, cnt)]
            ans %= MOD

    print(ans)


def __starting_point():
    main()

__starting_point()

n,k = map(int,input().split())
ans = k
mod = 10**9+7
v = [[0] for i in range(n+1)]
for i in range(n-1):
    a,b = map(int,input().split())
    v[a].append(b)
    v[b].append(a)
if n == 1:
    print(k)
elif n == 2:
    print(k*(k-1))
else:
    q = [1]
    v[1][0] = 1
    # print(v)
    while q:
        t = q.pop()
        # print(t,ans,len(v[t]))
        cnt = 2-(t==1)
        for i in range(1,len(v[t])):
            # print(i)
            if v[v[t][i]][0] == 0:
                q.append(v[t][i])
                v[v[t][i]][0] = 1
                ans = (ans*(k-cnt)) % mod
                cnt += 1
                # if cnt == k+1:
                #     print(t,i,"Err")
    # print(v)
    print(ans)

from collections import deque

N,K=map(int,input().split())
mod = 10**9+7
G=[[] for _ in range(N)]
for i in range(N-1):
  a,b=map(int,input().split())
  G[a-1].append(b-1)
  G[b-1].append(a-1)

def bfs(s):
    seen = [0]*N
    prev = [0]*N
    color = [0]*N
    todo = deque()
    seen[s]=1
    todo.append(s)
    color[s]=K
    while todo:
      a = todo.popleft()
      if a == start: count = K-1
      else: count = K-2
      for b in G[a]:
        if seen[b] == 0:
          seen[b] = 1
          todo.append(b)
          prev[b] = a
          color[b] = count %mod
          count -= 1
    return color
  
MAX,start = 0,-1
for i in range(N):
  if len(G[i])>MAX:
    MAX=len(G[i])
    start = i
    
color = bfs(start)
ans = 1
for i in range(N):
  ans *= color[i]
  ans %= mod
  
print(ans)

#!/usr/bin python3
# -*- coding: utf-8 -*-

# 双方向グラフで幅優先探索

from collections import deque

mod = 10**9+7

n, k = map(int, input().split())
graph = [[] for _ in range(n)]
#隣接リストの作成
for i in range(n-1):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    graph[a].append(b)
    graph[b].append(a)

#幅優先探索
q = deque()
seen = [False]*n
parent = [-1]*n
q.append(0)
seen[0] = True
parent[0] = 0
ret = k
while len(q)>0:
    cur = q.popleft()
    if cur == 0:
        cnt = k-1
    else:
        cnt = k-2
    for i in graph[cur]:
        if seen[i]==False:
            seen[i] = True
            #親
            parent[i] = cur
            q.append(i)
            ret *= cnt
            ret %= mod
            cnt -= 1
print(ret)

import sys
sys.setrecursionlimit(10**9)
mod = 10**9+7
N,K = map(int,input().split())
g = [[] for _ in range(N)]
for i in range(N-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)


ans = K
def rec(c,p):
    nonlocal ans
    if c == 0:
        for i in range(len(g[0])):
            ans *= K-i-1
            ans %= mod
        for v in g[c]:
            if v != p:
                rec(v,c)
    else:
        for i in range(len(g[c])-1):
            ans *= K-i-2
            ans %= mod
        for v in g[c]:
            if v != p:
                rec(v,c)


rec(0,0)
print(ans)

import sys
from collections import deque

mod = 10**9 + 7
input = sys.stdin.readline
N, K = map(int, input().split())

paths = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    paths[a-1].append(b-1)
    paths[b-1].append(a-1)

q = deque()
q.append((0, K, 0))

dp = 1
visited = set()
while q:
    node, count, d = q.popleft()
    if node in visited:
        continue
    dp *= count
    dp %= mod
    visited.add(node)

    res = K
    if d == 0:
        res -= 1
    else:
        res -= 2
    for n_node in paths[node]:
        if n_node not in visited:
            # print(n_node, res)
            q.append((n_node, res, d+1))
            res -= 1

print(dp)

import sys
sys.setrecursionlimit(1000000000)

mod = 10 ** 9 + 7
def dfs(v, p, k):
    ret = 1
    if len(graph[v]) > k:
        return 0
    kc = k - 2
    if p == -1:
        kc = k - 1
    for vi in graph[v]:
        if vi != p:
            ret *= kc
            ret = ret % mod
            kc -= 1
    for vi in graph[v]:
        if vi != p:
            ret *= dfs(vi, v, k)
            ret = ret % mod
    return ret

n, k = list(map(int, input().split()))
graph = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b = list(map(int, input().split()))
    graph[a - 1].append(b - 1)
    graph[b - 1].append(a - 1)
    
print(((dfs(0, -1, k) * k) % mod))


import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

sys.setrecursionlimit(100005)

n, k = na()
g = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b = na()
    g[a - 1].append(b - 1)
    g[b - 1].append(a - 1)

mod = 10**9 + 7


def dfs(cur, par, k, g):
    ret = 1
    nc = 0 if par == -1 else 1
    for e in g[cur]:
        if e == par: continue
        nc += 1
        ret = ret * (k - nc) % mod
        ret = ret * dfs(e, cur, k, g) % mod
    return ret % mod


print((dfs(0, -1, k, g) * k % mod))


# https://atcoder.jp/contests/abc133/tasks/abc133_e

# あー解説あたまいい
# そのノードで塗れる色の候補を持つのではなくて、
# そのノードの子で塗れる通りの数を持っておく
# あるノードの子で塗れる通りの数は、親とそのノードで塗る色の通りも確定してると考えると、(K-2)P(子の数)となる。(自身が根のときは自身の色の通りも考慮して、(K)P(子の数+1)となる)
# これをdfsで実装すれば良い

import sys
from collections import defaultdict

sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def mina(*argv, sub=1): return list([x - sub for x in argv])
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def read_a_int(): return int(read())


def read_ints(): return list(map(int, read().split()))


MOD = 10**9 + 7

N, K = read_ints()
tree = defaultdict(lambda: [])
for _ in range(N - 1):
    a, b = read_ints()
    a, b = mina(a, b)
    tree[a].append(b)
    tree[b].append(a)


def perm_mod(n, r, mod=MOD):
    # assert n >= r
    ret = 1
    for _ in range(r):
        ret *= n
        ret %= mod
        n -= 1
    return ret


def dfs(u, p):  # 現在のuと親のp
    if len(tree[u]) == 1 and tree[u][0] == p:
        # 葉なので終了
        return 1
    ret = 1  # その地点までの通りの数
    for to in tree[u]:
        if to == p:
            continue
        ret *= dfs(to, u)
        ret %= MOD
    if p == -1:
        ret *= perm_mod(K, len(tree[u]) + 1)
    else:
        ret *= perm_mod(K - 2, len(tree[u]) - 1)

    return ret % MOD


print((dfs(0, -1)))


from collections import deque

def permutation(n, k):
    s = 1
    for _ in range(k):
        s *= n
        s %= mod
        n -= 1
    return s

def bfs():
    nonlocal ans
    q = deque()
    q.append([1, 0])
    visit[1] = 1
    while q:
        x, y = q.popleft()
        a = 0
        for i in T[x]:
            if visit[i] == 0:
                q.append([i, 1])
                visit[i] = 1
                a += 1
        b = k - y - 1
        if b - a < 0:
            print(0)
            return
        ans *= permutation(b, a)
        ans %= mod
    return 

n, k = map(int, input().split())
T = [[] for _ in range(n + 1)]
visit = [0] * (n + 1)
mod = pow(10, 9) + 7
for _ in range(n - 1):
    a, b = map(int, input().split())
    T[a].append(b)
    T[b].append(a)
ans = k
bfs()
print(ans)

def main():
  MOD =  10**9 + 7
  N, K = list(map(int, input().split()))
  ki = [[] for _ in range(N)]
  for i in range(N-1):
    a, b = list(map(int, input().split()))
    ki[a-1].append(b-1)
    ki[b-1].append(a-1)
  d = [-1] * N
  que = []
  ans = K
  d[0] = 1
  for i, nex in enumerate(ki[0]):
    d[nex] = 1
    ans *= (K-i-1)
    ans %= MOD
    que.append(nex)
  while len(que) > 0:
    now = que.pop(0)
    count = 2
    for nex in ki[now]:
      if d[nex] != -1:
        continue
      d[nex] = 1
      ans *= (K-count)
      count += 1
      ans %= MOD
      que.append(nex)
  print(ans)
  
def __starting_point():
  main()

__starting_point()

N, K = list(map(int,input().split()))
AB = [list(map(int,input().split())) for _ in range (N-1)]

import sys
sys.setrecursionlimit(10**9)
edge = [[] for _ in range(N)]
for u,v in AB:
    edge[u-1].append(v-1)
    edge[v-1].append(u-1)

MOD = 10**9+7
mod = 10 ** 9 + 7
MAX = K+10
fac = [0] * MAX
finv = [0] * MAX
inv = [0] * MAX
def cominit():
    fac[0] = 1
    fac[1] = 1
    finv[0] = 1
    finv[1] = 1
    inv[1] = 1
    for i in range(2,MAX):
        fac[i] = fac[i-1] * i % mod
        inv[i] = mod - inv[mod%i] * (mod//i) % mod
        finv[i] = finv[i-1] * inv[i] % mod
def cmb(n,r):
    if n < 0 or r < 0 or r > n:return 0
    if r > n/2: r = n-r        
    return fac[n] * (finv[r] * finv[n-r] % mod) % mod

def permu(n,r):
    if n<=0 or r<=0 or r>n: return 0
    return (fac[n]*finv[n-r])%MOD
cominit()



visited = [False]*N
visited[0] = True
def dfs(s,ans):
    M = len(edge[s])-1*(s!=0)
    if M==0:
        return ans
    if s==0:
        ans *= permu(K-1, M)
        ans %= MOD
    else:
        ans *= permu(K-2, M)
        ans %= MOD

    for nv in edge[s]:
        if visited[nv]:continue
        visited[nv] = True
        ans = dfs(nv, ans)
    
    return ans

print((dfs(0,K)%MOD))





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

MOD = 10**9 + 7

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

nums = [1] * N
def dfs(vNow, vPar):
    numCh = 0
    for v2 in adjL[vNow]:
        if v2 == vPar: continue
        dfs(v2, vNow)
        numCh += 1
    num = 1
    if vPar == -1:
        for i in range(K-numCh, K):
            num *= i
            num %= MOD
    else:
        for i in range(K-numCh-1, K-1):
            num *= i
            num %= MOD
    nums[vNow] = num

dfs(0, -1)

ans = K
for num in nums:
    ans *= num
    ans %= MOD

print(ans)


import sys
sys.setrecursionlimit(10**7)

MOD=10**9+7

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

MAX=10**6
fc=[1]*MAX
inv=[1]*MAX
ifc=[1]*MAX

for i in range(2,MAX):
    fc[i]=i*fc[i-1]%MOD
    inv[i]=MOD-(MOD//i)*inv[MOD%i]%MOD
    ifc[i]=inv[i]*ifc[i-1]%MOD

def comb(n,k):
    if n<0 or k<0 or n-k<0:
        return 0
    return fc[n]*ifc[n-k]%MOD*ifc[k]%MOD

def dfs(cur,par):
    ret=1
    ch=len(g[cur])
    if par!=-1:
        ch-=1
    
    if par==-1:
        ret=comb(K-1,ch)*fc[ch]%MOD
    else:
        ret=comb(K-2,ch)*fc[ch]%MOD
        
        
    for dst in g[cur]:
        if dst==par:
            continue
        ret=ret*dfs(dst,cur)%MOD
    return ret

ans=K*dfs(0,-1)%MOD
print(ans)


from collections import deque
import sys
input = sys.stdin.readline

mod = 10**9 + 7
INF = float("inf")

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

edges = [[] * N for _ in range(N)]
for _ in range(N - 1):
    # 頂点の番号を0-indexに直す
    a, b = [int(x) - 1 for x in input().split()]
    edges[a].append(b)
    edges[b].append(a)

# 0をrootとする
dq = deque([0])

# color[i] = i番目の頂点を塗ることが可能な色の数
# visitedの管理も兼ねている（別にvisited配列を作っても特に問題はない）
# 後述するように負の値が入ることを許しているので、-1や0などで初期化するのはNG
color = [INF] * N
color[0] = K

"""
root = 0 から末端に向かって調べる

子1, 子2, 子3, ...と複数の「未着色」の子がある場合、塗ることが出来る色の数は
K-1, K-2, K-3,... (p==0 の場合)
K-2, K-3, K-4,... (p!=0 の場合)　のようになる

子が十分多い場合、どこかで「0」になるので、ans = 0　となる
故に、色の数が負になっても答えには影響しない
"""

while dq:
    # 親となる頂点
    p = dq.popleft()
    # 親をpとした時の、「未着色」な子の数
    cnt = 0
    for c in edges[p]:
        if color[c] == INF:
            if p == 0:
                color[c] = (K - 1 - cnt) % mod
            else:
                color[c] = (K - 2 - cnt) % mod
            cnt += 1
            dq.append(c)

ans = 1
for i in range(N):
    ans = (ans * color[i]) % mod

print(ans)


import sys
sys.setrecursionlimit(100000)

N,K=map(int,input().split())
SIZE=10**5+1; MOD=10**9+7 #998244353 #ここを変更する
 
SIZE += 1
inv = [0]*SIZE  # inv[j] = j^{-1} mod MOD
fac = [0]*SIZE  # fac[j] = j! mod MOD
finv = [0]*SIZE # finv[j] = (j!)^{-1} mod MOD
inv[1] = 1
fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
for i in range(2,SIZE):
  inv[i] = MOD - (MOD//i)*inv[MOD%i]%MOD
  fac[i] = fac[i-1]*i%MOD
  finv[i]= finv[i-1]*inv[i]%MOD

def narabekae(n,r): #nPr mod MOD の計算
  if n-r<0:
    return 0
  return fac[n]*finv[n-r]%MOD

branch=[[] for _ in range(N)]
for i in range(N-1):
  a,b=map(int,input().split())
  branch[a-1].append(b-1)
  branch[b-1].append(a-1)

ans=1

def draw(parent,nord):
  nonlocal ans
  children=len(branch[nord])-(parent !=-1)
  if children==0:
    return
  #(K-2)*(K-1)*... をchildrenの数だけ掛ける。
  ans=ans*narabekae(K-1-(parent !=-1),children)%MOD
  for b in branch[nord]:
    if b != parent:
      draw(nord,b)

draw(-1,0)
print(ans*K%MOD)


import sys
from collections import defaultdict

# ----------

sys.setrecursionlimit(10 ** 7)
INF = float("inf")
MOD = 10 ** 9 + 7


def combination(n, k):
    if k > n - k:
        return combination(n, n - k)
    return fact[n] * ifact[k] * ifact[n - k]


def permitation(n, k):
    # nPk = nCk * k!
    res = combination(n, k) * fact[k]
    return res % MOD


N, K = list(map(int, input().split()))
to = defaultdict(list)
for i in range(N - 1):
    a, b = list(map(int, input().split()))
    a -= 1
    b -= 1
    to[a].append(b)
    to[b].append(a)

# nまでの階乗を前処理
n = 200005
fact = defaultdict(int)
fact[0] = 1
for i in range(1, n + 1):
    fact[i] = fact[i - 1] * i
    fact[i] %= MOD
# nまでの階乗の逆元を前処理
ifact = defaultdict(int)
ifact[n] = pow(fact[n], MOD - 2, MOD)
for i in reversed(list(range(1, n + 1))):
    ifact[i - 1] = ifact[i] * i
    ifact[i - 1] %= MOD


def dfs(v, p=-1):
    nonlocal ans
    for u in to[v]:
        if u == p:
            continue
        dfs(u, v)
    if p == -1:
        nk = K
        c = len(to[v]) + 1
    else:
        nk = K - 2
        c = len(to[v]) - 1
    ans *= permitation(nk, c)
    ans %= MOD


ans = 1
dfs(0)
print(ans)


import math 
import sys 
"""
def p(n,r):
    if n<r:
        return 1
    return math.factorial(n)//math.factorial(n-r)
"""
def main():
    input=sys.stdin.readline 
    N,K=list(map(int,input().split()))
    E=[[] for _ in range(N)]
    MOD = 10**9+7
    for _ in range(N-1):
        u,v=list(map(int,input().split()))
        u-=1
        v-=1
        E[u].append(v)
        E[v].append(u)

    if N==1:
        print(K)
        return

    color = [-1 for _ in range(N)]
    dp = [-1 for _ in range(N)]
    stack = []
    color[u]=1
    ans=K
    for i,v in enumerate(E[u]):
        stack.append(v)
        ans*=(K-i-1)
        ans%=MOD


    while stack:
        u=stack.pop()
        color[u]=1
        length=0
        for v in E[u]:
            if color[v]==-1:
                stack.append(v)
                length+=1
        if dp[length]==-1:
            tmp=1
            for i in range(K-1-length,K-1):
                tmp*= i 
                tmp%=MOD 
            ans*=tmp 
        else:
            ans*=dp[length]
        ans%=MOD

    print((ans%MOD))

def __starting_point():
    main()
    


__starting_point()

#!/usr/bin python3
# -*- coding: utf-8 -*-

# 双方向グラフで幅優先探索
from collections import deque
mod = 10**9+7
N = 10**6                   # 出力の制限
g1 = [1]*(N+1)              # 元テーブル
g2 = [1]*(N+1)              # 逆元テーブル
for i in range(2, N + 1 ): # 準備
    g1[i] = ( g1[i-1] * i ) % mod
g2[N] = pow(g1[-1], mod-2, mod)
for i in range(N, 0, -1):
    g2[i-1] = ( g2[i] * i ) % mod

def nCr(n, r):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

def nPr(n, r):
    if ( r<0 or r>n ):
        return 0
    return g1[n] * g2[n-r] % mod

n, k = map(int, input().split())
graph = [[] for _ in range(n)]
#隣接リストの作成
for i in range(n-1):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    graph[a].append(b)
    graph[b].append(a)

#幅優先探索
q = deque()
seen = [False]*n
parent = [-1]*n
q.append(0)
seen[0] = True
parent[0] = 0
ret = k
while len(q)>0:
    cur = q.popleft()
    if cur == 0:
        cnt = k-1
    else:
        cnt = k-2
    for i in graph[cur]:
        if seen[i]==False:
            seen[i] = True
            #親
            parent[i] = cur
            q.append(i)
            ret *= cnt
            ret %= mod
            cnt -= 1
print(ret)

from sys import stdin
from collections import deque
def main():
    #入力
    readline=stdin.readline
    mod=10**9+7
    n,k=map(int,readline().split())
    G=[[] for _ in range(n)]
    for i in range(n-1):
        a,b=map(lambda x:int(x)-1,readline().split())
        G[a].append(b)
        G[b].append(a)

    ans=k
    stack=deque([0])
    flags=[False]*n
    flags[0]=True
    #dfs
    while len(stack)>0:
        now=stack.pop()
        if now==0:
            ans*=P(k-1,len(G[0]),mod)
            ans%=mod
        else:
            ans*=P(k-2,len(G[now])-1,mod)
            ans%=mod
        for nex in G[now]:
            if flags[nex]==False:
                flags[nex]=True
                stack.append(nex)

    print(ans)

def P(n,k,mod):
    res=1
    for m in range(n,n-k,-1):
        res*=m
        res%=mod
    return res

def __starting_point():
    main()
__starting_point()

import sys
from collections import deque
MOD = 10 ** 9 + 7

n, k, *ab = map(int, sys.stdin.read().split())
graph = [[] for _ in range(n)]
for a, b in zip(*[iter(ab)] * 2):
  a -= 1; b -= 1
  graph[a].append(b)
  graph[b].append(a)

def main():
  for i in range(n):
    if len(graph[i]) + 1 > k:
      print(0)
      return
  
  cnt = [None] * n; cnt[0] = k
  parent = [None] * n
  stack = [0]
  while stack:
    u = stack.pop()
    c = k - 2 if not parent[u] is None else k - 1
    for v in graph[u]:
      if v == parent[u]: continue 
      parent[v] = u
      cnt[v] = c
      c -= 1
      stack.append(v)

  res = 1
  for c in cnt:
    res *= c
    res %= MOD
  print(res)

def __starting_point():
  main()
__starting_point()

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
n, k = list(map(int, input().split()))
edges = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = list([int(x)-1 for x in input().split()])
    edges[a].append(b)
    edges[b].append(a)
MOD = 10**9+7
INF = 10**10
dp = [INF]*n


def dfs(v, parent, x):
    dp[v] = x
    if parent == -1:
        next_x = k-1
    else:
        next_x = k-2
    for v2 in edges[v]:
        if v2 == parent:
            continue
        dfs(v2, v, next_x)
        next_x -= 1


dfs(0, -1, k)
ans = 1
for x in dp:
    ans = ans*x % MOD
print(ans)


from collections import deque

int1 = lambda x: int(x) - 1
MOD = 10 ** 9 + 7

N, K = list(map(int, input().split()))
T = [[] for _ in range(N)]

for i in range(N - 1):
    a, b = list(map(int1, input().split()))
    T[a].append(b)
    T[b].append(a)

# dfs
ans = K
for i in range(len(T[0])):
    ans = (ans * (K - i - 1)) % MOD
D = deque(T[0])
visited = {0}

while D:
    v = D.pop()
    visited.add(v)
    for i in range(len(T[v]) - 1):
        ans = (ans * (K - i - 2)) % MOD
    for x in T[v]:
        if x not in visited:
            D.append(x)
print(ans)


import sys
sys.setrecursionlimit(410000)

mod = 10**9+7

def dfs(v,pr,k):
  if len(G[v]) > k:
    return 0
  
  kc = k-2
  if pr == -1:
    kc = k-1  
  
  ret = 1
  
  for vi in G[v]:
    if vi == pr:
      continue
    ret *= kc
    ret %= mod
    kc -= 1
    
  for vi in G[v]:
    if vi == pr:
      continue
    ret *= dfs(vi,v,k)
    ret %= mod
  
  return ret


n,k = map(int,input().split())
G = [[] for i in range(n)]
for i in range(n-1):
  a,b = map(int,input().split())
  G[a-1].append(b-1)
  G[b-1].append(a-1)      
  
print(dfs(0,-1,k) * k % mod )

# coding: utf-8
# Your code here!
import sys

sys.setrecursionlimit(10**9)

def dfs(num):
    temp=K-len(way[num])
    
    for w in way[num]:
        if visited[w]==-1:
            visited[w]=temp
            temp+=1
            dfs(w)
    
    return 

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

mod=10**9+7

visited=[-1]*N
way=[[] for i in range(N)]

for _ in range(N-1):
    a,b=list(map(int,input().split()))
    way[a-1].append(b-1)
    way[b-1].append(a-1)
    
color=[]
visited[0]=K
dfs(0)

#print(way)
#print(visited)
ans=1
for item in visited:
    ans*=item
    ans%=mod
print(ans)


import sys
sys.setrecursionlimit(10**6)

MOD = 10**9+7

N,K = map(int,input().split())
edge = [[] for _ in range(N)]

for _ in range(N-1):
    a,b = map(int,input().split())
    a,b = a-1,b-1
    edge[a].append(b)
    edge[b].append(a)

    
visit = [0]*N

def dfs(vs, pat, count):
    
    for ve in edge[vs]:
        if visit[ve]:continue
        
        visit[ve] = 1
        pat = pat*(K-count) % MOD
        count += 1
        pat = dfs(ve, pat, 2)
    
    return pat

visit[0] = 1

ans = dfs(0,K,1)
print(ans)

from collections import defaultdict
from collections import deque
import sys
sys.setrecursionlimit(10**6)

N, K = list(map(int, input().split()))
ab = defaultdict(list)
for i in range(N-1):
    a, b = list(map(int, input().split()))
    ab[a-1].append(b-1)
    ab[b-1].append(a-1)

MOD = 10**9+7


def dfs(v, pv, n):
    k = K-1 if pv == -1 else K-2
    a = 1
    for u in ab[v]:
        if u != pv:
            a *= dfs(u, v, k)
            a %= MOD
            k -= 1
    return a*n % MOD


print((dfs(0, -1, K)))


import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, K, *AB = list(map(int, read().split()))
    G = [[] for _ in range(N)]
    for a, b in zip(AB[::2], AB[1::2]):
        G[a - 1].append(b - 1)
        G[b - 1].append(a - 1)

    COM_MAX = K

    fac, finv, inv = [0] * (COM_MAX + 1), [0] * (COM_MAX + 1), [0] * (COM_MAX + 1)
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1

    for i in range(2, COM_MAX + 1):
        fac[i] = fac[i - 1] * i % MOD
        inv[i] = MOD - inv[MOD % i] * (MOD // i) % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD

    def mod_perm(n, r):
        if n < r:
            return 0
        if n < 0 or r < 0:
            return 0
        return fac[n] * (finv[n - r] % MOD) % MOD

    stack = deque([0])
    order = []
    parent = [-1] * N
    while stack:
        v = stack.pop()
        order.append(v)
        for nv in G[v]:
            if nv != parent[v]:
                stack.append(nv)
                parent[nv] = v

    A = [0] * N
    for v in reversed(order):
        tmp = 1
        child = 0
        for nv in G[v]:
            if nv != parent[v]:
                tmp = tmp * A[nv] % MOD
                child += 1

        colors = K if v == 0 else K - 2
        nodes = child + 1 if v == 0 else child

        A[v] = tmp * mod_perm(colors, nodes) % MOD

    print((A[0]))
    return


def __starting_point():
    main()

__starting_point()

import sys
sys.setrecursionlimit(500000)

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

T = [[] for i in range(N)]
for i in range(N-1):
    a, b = map(int,input().split())
    T[a-1].append(b-1)
    T[b-1].append(a-1)

ans = 1
def dfs(i, bb, b, p):
    nonlocal ans
    ans = (ans*(K-bb-b))%(10**9+7)
    cnt = 0
    for j in T[i]:
        if j == p:
            continue
        dfs(j, b + cnt, 1, i)
        cnt += 1

dfs(0, 0, 0, -1)
print(ans)

from sys import setrecursionlimit
setrecursionlimit(10**6)
n,k=map(int,input().split())
paths=[[] for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    paths[a-1].append(b-1)
    paths[b-1].append(a-1)
inf=100000000000000
nums=[-inf]*n
nums[0]=k
from collections import deque
now=deque()
now.append(0)
def bfs(d):
    nonlocal n,k,paths,nums,now
    l=len(now)
    if d==1:
        for i in range(l):
            p=now.popleft()
            ln=len(paths[p])
            next_num=k-1
            for j in range(ln):
                if nums[paths[p][j]]==-inf:
                    nums[paths[p][j]]=next_num
                    now.append(paths[p][j])
                    next_num-=1
    else:
        for i in range(l):
            p=now.popleft()
            ln=len(paths[p])
            next_num=k-2
            for j in range(ln):
                if nums[paths[p][j]]==-inf:
                    nums[paths[p][j]]=next_num
                    now.append(paths[p][j])
                    next_num-=1
    if len(now):bfs(d+1)
bfs(1)
ans=1
for i in range(n):
    if nums[i]<=0:
        print(0)
        return
    ans*=nums[i]
    ans%=(10**9+7)
print(ans)

# coding: utf-8
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, K = lr()
graph = [[] for _ in range(N+1)]  # 1-indexed
for _ in range(N-1):
    a, b = lr()
    graph[a].append(b)
    graph[b].append(a)

MOD = 10 ** 9 + 7

def perm(n,k):
    if k > n or k < 0: return 0
    return fact[n] * fact_inv[n-k] % MOD

def cmb(n, k):
    if k < 0 or k > n: return 0
    return fact[n] * fact_inv[k] % MOD * fact_inv[n-k] % MOD

def cumprod(arr, MOD):
    L = len(arr); Lsq = int(L**.5+1)
    arr = np.resize(arr, Lsq**2).reshape(Lsq, Lsq)
    for n in range(1, Lsq):
        arr[:, n] *= arr[:, n-1]; arr[:, n] %= MOD
    for n in range(1, Lsq):
        arr[n] *= arr[n-1, -1]; arr[n] %= MOD
    return arr.ravel()[:L]

def make_fact(U, MOD):
    x = np.arange(U, dtype=np.int64); x[0] = 1
    fact = cumprod(x, MOD)
    x = np.arange(U, 0, -1, dtype=np.int64); x[0] = pow(int(fact[-1]), MOD-2, MOD)
    fact_inv = cumprod(x, MOD)[::-1]
    return fact, fact_inv

U = 10 ** 6  # 階乗テーブルの上限
fact, fact_inv = make_fact(U, MOD)
#print(answer % MOD)
# np.int64とint型の違いに注意
answer = 1
root = 1
parent = [0] * (N+1)
order = []
stack = [root]
answer = K * perm(K-1, len(graph[root])) % MOD
while stack:
    cur = stack.pop()
    order.append(cur)
    if cur != 1:
        answer *= perm(K-2, len(graph[cur])-1)
        answer %= MOD
    for next in graph[cur]:
        if next == parent[cur]:
            continue
        parent[next] = cur
        stack.append(next)

print((answer%MOD))


from collections import deque
n, k = map(int, input().split())
inf = pow(10, 9)+7

tree = [[] for _ in range(n)]
for i in range(n-1):
  a, b = map(int, input().split())
  tree[a-1].append(b-1)
  tree[b-1].append(a-1)

not_yet = deque(tree[0])
already = [False]*n
already[0] = True
ans = k
key = k-1
for v in tree[0]:
  already[v] = True
  ans *= key
  ans %= inf
  key -= 1

while not_yet:
  key = not_yet.popleft()
  for v in range(k-2, k-1-len(tree[key]), -1):
    ans *= v
    ans %= inf
  
  for value in tree[key]:
    if already[value]:
      continue
    not_yet.append(value)
    already[value] = True

print(ans)

import sys
def input():return sys.stdin.readline().strip()

from collections import deque


def main():
    N, K = map(int, input().split())
    to = [[] for _ in range(N)]
    MOD = 10**9 + 7
    for _ in range(N-1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        to[a].append(b)
        to[b].append(a)

    MAX_N = 3 * 10 ** 5
    MOD = 10 ** 9 + 7
    fac = [0]*MAX_N
    inv = [0]*MAX_N
    finv = [0]*MAX_N
    fac[0] = 1; fac[1] = 1
    inv[1] = 1
    finv[0] = 1; finv[1] = 1

    def com_init():
        for i in range(2, MAX_N):
            fac[i] = fac[i-1] * i % MOD
            inv[i] = -(MOD//i)*inv[MOD%i]%MOD
            finv[i] = finv[i-1]*inv[i]%MOD

    def perm(n, r):
        if n < 0:return 0
        elif r > n: return 0
        
        return fac[n]*finv[n-r]%MOD
    
    # dfs
    com_init()
    def dfs(s):
        stack = deque()
        stack.append((s, -1)) # now, par
        res = K
        while stack:
            now, par = stack.pop()

            if now == 0:
                children = len(to[now])
            else:
                children = len(to[now]) - 1

            if now == 0:
                nx_col = K - 1
            else:
                nx_col = K - 2
            
            res *= perm(nx_col, children)
            res %= MOD

            if children == 0 and now != 0:
                continue
            
            for nv in to[now]:
                if nv != par:
                    stack.append((nv, now))
        return res
    ans = dfs(0)
    print(ans)

def __starting_point():
    main()
__starting_point()

import networkx as nx

int1 = lambda x: int(x) - 1
MOD = 10 ** 9 + 7

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

G = nx.Graph()
G.add_nodes_from(list(range(N)))
G.add_edges_from([tuple(map(int1, input().split())) for _ in range(N - 1)])

ans = K
for i in range(nx.degree(G)[0]):
    ans = (ans * (K - i - 1)) % MOD

for parent, child in nx.dfs_edges(G, 0):
    for i in range(nx.degree(G)[child] - 1):
        ans = (ans * (K - i - 2)) % MOD

print(ans)


import sys


sys.setrecursionlimit(10 ** 6)


def main():
    MOD = 10 ** 9 + 7
    N, K = list(map(int, input().split(' ')))
    adj = [[] for _ in range(N)]
    for _ in range(N - 1):
        a, b = list(map(lambda x: int(x) - 1, input().split(' ')))
        adj[a].append(b)
        adj[b].append(a)
    if K <= 2:
        if N <= K:
            p = 1
            for n in range(N):
                p *= K - n
            print(p % MOD)
        else:
            print(0)
        return
    p = 1
    perm_k1 = [0 for _ in range(K)]
    for k in range(K):
        perm_k1[k] = p
        p *= K - 1 - k
        p %= MOD
    perm_k2 = [0 for _ in range(K - 1)]
    p = 1
    for k in range(K - 1):
        perm_k2[k] = p
        p *= K - 2 - k
        p %= MOD

    def dfs(n=0, p=-1):
        # node, parentの色を固定した時の色の塗り方
        children = [c for c in adj[n] if c != p]
        if len(children) == 0:
            return 1
        n_colors = K - 2 if n != 0 else K - 1
        if n_colors < len(children):
            return 0
        ret = perm_k2[len(children)] if n != 0 else perm_k1[len(children)]
        for c in children:
            ret *= dfs(c, n)
            ret %= MOD
        return ret

    print((K * dfs()) % MOD)


def __starting_point():
    main()
__starting_point()

import sys
sys.setrecursionlimit(410000)

mod = 10 ** 9 + 7
def dfs(v, p, k):
    ret = 1
    if len(graph[v]) > k:
        return 0
    kc = k - 2
    if p == -1:
        kc = k - 1
    for vi in graph[v]:
        if vi != p:
            ret *= kc
            ret = ret % mod
            kc -= 1
    for vi in graph[v]:
        if vi != p:
            ret *= dfs(vi, v, k)
            ret = ret % mod
    return ret

n, k = map(int, input().split())
graph = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b = map(int, input().split())
    graph[a - 1].append(b - 1)
    graph[b - 1].append(a - 1)
    
print((dfs(0, -1, k) * k) % mod)

import sys
sys.setrecursionlimit(10**9)
class Combination:
  def __init__(self, n_max, mod=10**9+7):
    self.mod = mod
    self.modinv = self.make_modinv_list(n_max)
    self.fac, self.facinv = self.make_factorial_list(n_max)

  def __call__(self, n, r):
    return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

  def make_factorial_list(self, n):
    # 階乗のリストと階乗のmod逆元のリストを返す O(n)
    # self.make_modinv_list()が先に実行されている必要がある
    fac = [1]
    facinv = [1]
    for i in range(1, n+1):
      fac.append(fac[i-1] * i % self.mod)
      facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
    return fac, facinv

  def make_modinv_list(self, n):
    # 0からnまでのmod逆元のリストを返す O(n)
    modinv = [0] * (n+1)
    modinv[1] = 1
    for i in range(2, n+1):
        modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
    return modinv

N,K = map(int,input().split())
adj = [ [ ]for _ in range(N) ]
comb = Combination(10**5)

def nPr(n,r):
  if n < r: return 0
  return comb(n, r) * comb.fac[r]

for _ in range(N-1):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  adj[a].append(b)
  adj[b].append(a)

def dfs(v, p=-1):
  nonlocal ans
  c = 0
  for nei in adj[v]:
    if nei == p: continue
    c += 1
    dfs(nei, v)

  nk = K-1 if p==-1 else K-2
  ans *= nPr(nk, c)
  ans %= 10**9+7

ans = K
dfs(0)
print(ans)

import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)


def read():
    N, K = list(map(int, input().strip().split()))
    G = [[] for i in range(N+1)]
    for i in range(N-1):
        a, b = list(map(int, input().strip().split()))
        G[a-1].append(b-1)
        G[b-1].append(a-1)
    return N, K, G


def permute_init(n, MOD):
    factorial = [1 for i in range(n+1)]
    for i in range(1, n+1):
        factorial[i] = factorial[i-1] * i
        factorial[i] %= MOD
    return factorial


def permute(n, r, factorial, MOD):
    """nPr = n! / (n-r)!"""
    if n < 0 or r < 0 or n < r:
        return 0
    return factorial[n] * pow(factorial[n-r], MOD-2, MOD) % MOD


def solve(N, K, G, MOD=10**9+7):
    factorial = permute_init(K, MOD)

    visited = [False for i in range(N)]
    
    def dfs(a=0):
        f = 1
        if a == 0:
            f = permute(K-1, len(G[a]), factorial, MOD)
        else:
            f = permute(K-2, len(G[a])-1, factorial, MOD)
        for b in G[a]:
            if not visited[b]:
                visited[b] = True
                f *= dfs(b)
                f %= MOD
        return f
    
    visited[0] = True
    ans = K * dfs(0) % MOD

    return ans


def __starting_point():
    inputs = read()
    print(("%s" % solve(*inputs)))

__starting_point()

import sys
from collections import defaultdict

# ----------

sys.setrecursionlimit(10 ** 7)
INF = float("inf")
MOD = 10 ** 9 + 7


def combination(n, k):
    if k > n - k:
        return combination(n, n - k)
    return fact[n] * ifact[k] * ifact[n - k]


def permitation(n, k):
    # nPk = nCk * k!
    if n < 0:
        return 0
    res = combination(n, k) * fact[k]
    return res % MOD


N, K = list(map(int, input().split()))
to = defaultdict(list)
for i in range(N - 1):
    a, b = list(map(int, input().split()))
    a -= 1
    b -= 1
    to[a].append(b)
    to[b].append(a)

# nまでの階乗を前処理
n = 200005
fact = defaultdict(int)
fact[0] = 1
for i in range(1, n + 1):
    fact[i] = fact[i - 1] * i
    fact[i] %= MOD
# nまでの階乗の逆元を前処理
ifact = defaultdict(int)
ifact[n] = pow(fact[n], MOD - 2, MOD)
for i in reversed(list(range(1, n + 1))):
    ifact[i - 1] = ifact[i] * i
    ifact[i - 1] %= MOD


def dfs(v, p=-1):
    nonlocal ans
    for u in to[v]:
        if u == p:
            continue
        dfs(u, v)
    if p == -1:
        nk = K
        c = len(to[v]) + 1
    else:
        nk = K - 2
        c = len(to[v]) - 1
    ans *= permitation(nk, c)
    ans %= MOD


ans = 1
dfs(0)
print(ans)


import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7
res = 1


def resolve():
    def dfs(v, p, c):
        nonlocal res
        res = (res * c) % mod
        c = k - 1 if p == -1 else k - 2
        for u in edge[v]:
            if u != p:
                dfs(u, v, c)
                c -= 1

    n, k = list(map(int, input().split()))
    edge = [[] for _ in range(n)]
    for _ in range(n - 1):
        a, b = list(map(int, input().split()))
        edge[a - 1].append(b - 1)
        edge[b - 1].append(a - 1)

    dfs(0, -1, k)
    print(res)


def __starting_point():
    resolve()

__starting_point()

# Review problem

from collections import defaultdict
import sys
sys.setrecursionlimit(10**7)
N, K = map(int, input().split())
graph = [[] for i in range(N+1)]
for _ in range(N-1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
visited = [0 for i in range(N+1)]
dis = [0 for i in range(N+1)]
parent = [-1 for i in range(N+1)]
parent[1] = -1
visited[1] = True
mod = 10**9+7


def bfs(node):
    for child in graph[node]:
        if visited[child] == False:
            visited[child] = True
            parent[child] = node
            dis[child] = dis[node]+1
            bfs(child)


bfs(1)

par_data = defaultdict(int)
for i in range(1, N+1):
    x = parent[i]
    par_data[x] += 1
ans = K
for parent in par_data.keys():
    if parent > 0:
        X = par_data[parent]
        if parent == 1:
            for i in range(X):
                ans = ans*(K-1-i)
                ans %= mod
                if ans==0:
                  print(0)
                  return
        else:
            for i in range(X):
                ans = ans*(K-2-i)
                ans %= mod
                if ans==0:
                  print(0)
                  return
print(ans)

import sys
from collections import deque

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, k = list(map(int, input().split()))
    edge = [[] for _ in range(n)]
    for _ in range(n - 1):
        a, b = list(map(int, input().split()))
        edge[a - 1].append(b - 1)
        edge[b - 1].append(a - 1)

    res = k
    que = deque([0])
    visited = [False] * n
    visited[0] = True
    while que:
        v = que.popleft()
        cnt = 0
        for u in edge[v]:
            if not visited[u]:
                visited[u] = True
                cnt += 1
                que.append(u)
        if v == 0:
            for i in range(cnt):
                res *= (k - 1 - i)
                res %= mod
        else:
            for i in range(cnt):
                res *= (k - 2 - i)
                res %= mod
    print(res)


def __starting_point():
    resolve()

__starting_point()

import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_adjlist_nond(n, edges):
    res = [[] for _ in range(n+1)]
    for edge in edges:
        res[edge[0]].append(edge[1])
        res[edge[1]].append(edge[0])
    return res


def main():
    N, K = NMI()
    edges = [NLI() for _ in range(N-1)]
    tree = make_adjlist_nond(N, edges)
    stack = deque()
    stack.append(1)
    ans = K
    seen = [False] * (N+1)
    while stack:
        now = stack.pop()
        seen[now] = True
        tmp = K - 2
        if now == 1:
            tmp += 1
        cnt = 0
        for i, goto in enumerate(tree[now]):
            if seen[goto]:
                cnt += 1
                continue
            ans = ans * (tmp - i + cnt) % MOD
            stack.append(goto)

    print(ans % MOD)


def __starting_point():
    main()
__starting_point()

#!/usr/bin/env python3

MOD = 10 ** 9 + 7

def main():
    n, k = list(map(int, input().split()))
    adj = [[] for i in range(n)]
    for i in range(n - 1):
        a, b = list(map(int, input().split()))
        a -= 1
        b -= 1
        adj[a].append(b)
        adj[b].append(a)

    res = k
    stack = [0]
    visited = [False for i in range(n)]
    while stack:
        i = stack.pop()
        visited[i] = True
        children = [x for x in adj[i] if not visited[x]]
        res *= perm((k - 1 if i == 0 else k - 2), len(children))
        res %= MOD
        for c in children:
            stack.append(c)
    print(res)

def perm(t, s):
    res = 1
    for i in range(s):
        res *= t
        res %= MOD
        t -= 1
    return res

def __starting_point():
    main()

__starting_point()

import sys
sys.setrecursionlimit(100000000)
N, K = list(map(int, input().split()))
ab = [list(map(int, input().split())) for i in range(N-1)]
graph = [[] for _ in range(N)]
used = [-1]*N
ans = K
mod = 10**9+7

for a, b in ab:
  a -= 1
  b -= 1
  graph[a] += [b]
  graph[b] += [a]


def npr(n, r, p):
  e = 1
  for i in range(n, n-r, -1):
    e *= i
    e %= p

  return e

def dfs(u, pre):
  nonlocal ans
  child = 0
  for v in graph[u]:
    if v != pre:
      dfs(v, u)
      child += 1
  if u == 0:
    ans *= npr(K-1, child, mod)
  else:
    ans *= npr(K-2, child, mod)

  ans %= mod

dfs(0, -1)
print(ans)


import sys
sys.setrecursionlimit(10**7)
n,k = map(int,input().split())
li = [[] for _ in range(n+1)]
mod = 10**9+7
ans = k
perm = [1]*(n)# 組み合わせ(k-2)P(要素)

for i in range(n-1):
    a,b = map(int,input().split())
    li[a].append(b)
    li[b].append(a)
    perm[i+1] = (perm[i]*(k-2-i))%mod

def dfs(now,before):
    point = 1
    if now == 1:
        ret = 1
        ko = len(li[1])
        for i in range(ko):
            ret *= k-1-i
            ret %= mod
    else:
        ko = len(li[now])-1
        ret= perm[ko]%mod
    
    for i in li[now]:
        if i==before:
            continue
        ret = ret*dfs(i,now)%mod
    return ret

ans *= dfs(1,0)

print(ans%mod)

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
MOD = 10**9+7
N,K = map(int,input().split())
edge = [[] for _ in range(N)]
for i in range(N-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    edge[a].append(b)
    edge[b].append(a)

ans = 1
def dfs(now, par,num):
    nonlocal ans
    ans = ans*num%MOD
    num = K-1
    if par != -1:
        num -= 1
    for ch in edge[now]:
        if ch != par:
            dfs(ch,now,num)
            num -= 1

dfs(0,-1,K)
print(ans)

import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readlines

from collections import deque

def main():

    lines = input()
    n, k = list(map(int, lines[0].split()))
    a = [[] for i in range(n+1)]

    for i in range(1, n):
        r, l = list(map(int, lines[i].split()))
        a[r].append(l)
        a[l].append(r)

    que = deque()
    que.append(1)
    colors = [-1] * (n+1)
    colors[1] = k
    ways = k

    while que:
        p = que.popleft()
        # root no toki
        if p == 1:
            now_color = k
            for son in a[p]:
                now_color -= 1
                ways = (ways * now_color) % 1_000_000_007
                colors[son] = now_color
                que.append(son)
        else:
            now_color = k-1
            for son in a[p]:
                if colors[son] < 0:
                    now_color -= 1
                    colors[son] = now_color
                    ways = (ways * now_color) % 1_000_000_007
                    que.append(son)

    print(ways)

main()



#!/usr/bin/env python3

MOD = 10 ** 9 + 7

def main():
    n, k = list(map(int, input().split()))
    adj = [[] for i in range(n)]
    for i in range(n - 1):
        a, b = list(map(int, input().split()))
        a -= 1
        b -= 1
        adj[a].append(b)
        adj[b].append(a)
    res = k
    stack = [0]
    visited = [False for i in range(n)]
    while stack:
        i = stack.pop()
        visited[i] = True
        children = [x for x in adj[i] if not visited[x]]
        res *= perm((k - 1 if i == 0 else k - 2), len(children))
        res %= MOD
        for c in children:
            stack.append(c)
    print(res)

def perm(t, s):
    if s > t:
        return 0
    res = 1
    for i in range(s):
        res *= t
        res %= MOD
        t -= 1
    return res

def __starting_point():
    main()

__starting_point()

import sys
from collections import deque
sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし


N,K = MI()
mod = 10**9+7
Graph = [[] for _ in range(N+1)]
for _ in range(N-1):
    a,b = MI()
    Graph[a].append(b)
    Graph[b].append(a)

ans = K

for i in range(len(Graph[1])):
    ans *= K-i-1
    ans %= mod
deq = deque([d for d in Graph[1]])
flag = [0]*(N+1)
flag[1] = 1
for d in Graph[1]:
    flag[d] = 1

while deq:
    n = deq.pop()
    for i in range(len(Graph[n])-1):
        ans *= K-2-i
        ans %= mod
    for d in Graph[n]:
        if flag[d] == 0:
            flag[d] = 1
            deq.appendleft(d)

print(ans)


def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math

    #inf = 10**17
    mod = 10**9 + 7

    n,k = map(int, input().split())
    adj = [[] for _ in range(n)] #頂点数, 場合によって変える
    for _ in range(n-1):
        a,b = map(int, input().split())
        adj[a-1].append(b-1)
        adj[b-1].append(a-1)

    def dfs(v, par, k):
        if par == -1:
            kk = k-1
        else:
            kk = k-2

        res = 1
        if v == 0:
            res *= k

        for i in range(len(adj[v])):
            nv = adj[v][i]
            if  nv == par:
                continue
            res *= kk * dfs(nv, v, k)
            res %= mod
            kk -= 1
        return res

    res = dfs(0, -1, k)
    print(res)

def __starting_point():
    main()
__starting_point()

mod = 10 ** 9 + 7
import sys
sys.setrecursionlimit(10 ** 7)
def dfs(u):
    cnt = 0
    res = 1
    for i in edges[u]:
        if visited[i] == -1:
            visited[i] = 0
            cnt += 1
            res *= dfs(i)
            res %= mod
    for i in range(cnt):
        res *= k - i - 2
        res %= mod
    return res
n, k = map(int, input().split())
edges = [[] for i in range(n)]
for i in range(n - 1):
    a, b = map(int, input().split())
    edges[a - 1].append(b - 1)
    edges[b - 1].append(a - 1)
visited = [-1] * n
visited[0] = 0
ans = k
for i in range(len(edges[0])):
    ans *= (k - i - 1)
    ans %= mod
for i in edges[0]:
    visited[i] = 0
    ans *= dfs(i)
    ans %= mod
print(ans)

mod = 10 ** 9 + 7

n, k = map(int, input().split())
edge = [[] for _ in range(n)]
parent = [0] * n
permutation_k2 = [1] * n
for i in range(n-1):
  a, b = map(int, input().split())
  edge[a-1].append(b-1)
  edge[b-1].append(a-1)
  permutation_k2[i+1] = permutation_k2[i] * (k - 2 - i) % mod
count = k * (k - 1) * permutation_k2[len(edge[0]) - 1] % mod
queue = edge[0]
while queue:
  vertex = queue.pop()
  count = count * permutation_k2[len(edge[vertex]) - 1] % mod
  p = parent[vertex]
  for v in edge[vertex]:
    if v == p:
      continue
    queue.append(v)
    parent[v] = vertex
if n == 1:
  print(k)
else:
  print(count)

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
N,K = map(int,input().split())
AB = [tuple(map(int,input().split())) for i in range(N-1)]

es = [[] for _ in range(N)]
for a,b in AB:
    a,b = a-1,b-1
    es[a].append(b)
    es[b].append(a)

MOD = 10**9+7
ans = K
def rec(v,p=-1,d=0):
    nonlocal ans
    k = K-2 if d else K-1
    for to in es[v]:
        if to==p: continue
        ans *= k
        ans %= MOD
        k -= 1
        rec(to,v,d+1)
rec(0)
print(ans)

import sys
sys.setrecursionlimit(10000000)
n,k=list(map(int,input().split()))
CONST=10**9+7
path={i:list() for i in range(n)}
for i in range(n-1):
  a,b=list(map(int,input().split()))
  path[a-1].append(b-1)
  path[b-1].append(a-1)
used=[0]*n
used[0]=1
  
def bfs(pos, parent):
  res=k-parent
  if parent>0:
    deg=2
  else:
    deg=1
  for nex in path[pos]:
    if used[nex]:
      continue
    used[nex]=1
    res *= bfs(nex,deg)
    res = res%CONST
    deg += 1
  return res%CONST
    
print((bfs(0, 0)))


import sys
sys.setrecursionlimit(10**6)

def iig(vn, en):
    res = [[] for _ in range(vn)]
    for _ in range(en):
        ai, bi = [int(x) - 1 for x in input().split()]
        res[ai].append(bi)
        res[bi].append(ai)
    return res

def sep_pc(graph, root=0):
    parent = [-1 for _ in range(n)]
    children = [None for _ in range(n)]
    def f(x, p):
        parent[x] = p
        children[x] = [y for y in graph[x] if y != p]
        for y in graph[x]:
            if y != p:
                f(y, x)
        return
    f(root, -1)
    return parent, children

def itree(n, root=0):
    return sep_pc(iig(n, n - 1), root)

mod = 10**9 + 7

fact_range = 10**5 + 3
facts = [1] * (fact_range + 1)
for i in range(0, fact_range):
    facts[i+1] = facts[i] * (i + 1) % mod

ifacts = [1] * (fact_range + 1)
ifacts[fact_range] = pow(facts[fact_range], mod - 2, mod)
for i in range(fact_range, 0, -1):
    ifacts[i-1] = ifacts[i] * i % mod

n, k = list(map(int, input().split()))
p, c = itree(n)
def dfs(i=0, cur=k, avail=k-1):
    sz = len(c[i])
    if avail <= 0 and sz > 0 or sz > avail:
        return 0
    cur = cur * facts[avail] * ifacts[avail - sz] % mod
    for u in c[i]:
        cur = dfs(u, cur, k - 2)
    return cur
print((dfs()))


import collections

n, k = map(int, input().split())
mod = 10 ** 9 + 7
graph = [[] for i in range(n + 1)]
for i in range(n - 1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
flag = [False for i in range(n + 1)]
flag[1] = True
queue = collections.deque([1])
ans = k
while queue:
    test = queue.popleft()
    temp = [flag[graph[test][i]] for i in range(len(graph[test]))].count(True)
    num = 0
    for i in range(len(graph[test])):
        if flag[graph[test][i]] == True:
            continue
        ans *= (k - temp - num - 1)
        ans %= mod
        num += 1
        queue.append(graph[test][i])
        flag[graph[test][i]] = True
print(ans)

import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**7)
n,k=map(int,input().split())
ab=[[]for _ in range(n)]
visited=[False]*n
for i in range(n-1):
	a,b=map(int,input().split())
	ab[a-1].append(b-1)
	ab[b-1].append(a-1)
ans=k
def dfs(i):
	nonlocal ans
	child=0
	visited[i]=True
	for x in ab[i]:
		if visited[x]==False:
			dfs(x)
			child+=1
	if i==0:
		ans*=p(k-1,child)
	else:
		ans*=p(k-2,child)
	ans%=mod
def p(a,b):
	e=1
	for i in range(a,a-b,-1):
		e*=i
		e%=mod
	return e	
mod=10**9+7
dfs(0)
print(ans)

# E - Virus Tree 2
# https://atcoder.jp/contests/abc133/tasks/abc133_e

from heapq import heapify, heappop, heappush

def permutation(n, k, MOD):
    s = 1
    for _ in range(k):
        s *= n
        s %= MOD
        n -= 1
    return s

def dfs(c):
  nonlocal ans
  q = [c]
  heapify(q)
  while q: 
    cur = heappop(q)
    if cur == 0:
      exclusion = 1
    else:
      exclusion = 2
    visited[cur] = True
    next_cnt = 0
    for i in edges[cur]:
      if not visited[i]:
        heappush(q, i)
        next_cnt += 1
    if k - exclusion - next_cnt < 0:
      print(0)
      return
    ans *= permutation(k - exclusion, next_cnt, MOD)
    ans %= MOD

n, k = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(n - 1)]
AB = [(a - 1, b - 1) for a, b in AB]

MOD = 10 ** 9 + 7

edges = [[] for _ in range(n)]
for itr, (a, b) in enumerate(AB):
  edges[a].append(b)
  edges[b].append(a)
  
visited = [False] * n

ans = k
dfs(0)

print(ans)

import sys
sys.setrecursionlimit(10**6)
n, k = map(int, input().split())
graph = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
ans = 1
mod = 10**9+7
def dfs(node, p_node=-1):
    if p_node==-1:
        tmp = k
        kk = k-1
    else:
        tmp = 1
        kk = k-2
    for c_node in graph[node]:
        if c_node==p_node:
            continue
        tmp *= dfs(c_node, node)
        tmp *= kk
        tmp %= mod
        kk -= 1
    return tmp
print(dfs(0))

# Python3 (3.4.3)
import sys
input = sys.stdin.readline

# -------------------------------------------------------------
# function
# -------------------------------------------------------------
class Modinv:
    def __init__(self, n, mod):
        self.mod = mod
        self.fact = [1]*n
        self.finv = [1]*n
        self.inv  = [1]*n
        for i in range(2,n):
            self.fact[i] = (self.fact[i-1]*i) % self.mod
            self.inv[i]  = self.mod - self.inv[self.mod%i] * (self.mod//i)%self.mod
            self.finv[i] = self.finv[i-1] * self.inv[i] % self.mod
 
    def nCr(self, n, r):
        if n<r:
            return 0
        else:
            return self.fact[n] * (self.finv[r] * self.finv[n-r] % self.mod) % self.mod
    
    def nPr(self, n, r):
        if n<r:
            return 0
        else:
            return self.fact[n] * self.finv[n-r] % self.mod

mod = 10**9+7

# -------------------------------------------------------------
# main
# -------------------------------------------------------------
N,K = map(int,input().split())
AB = [tuple(map(int,input().split())) for _ in range(N-1)]

A = [[] for _ in range(N)]
for a,b in AB:
    A[a-1].append(b-1)
    A[b-1].append(a-1)

Modinv = Modinv(K+10, mod)

# 頂点はK色どれでも塗ることが可能
ans = K

from collections import deque
dq = deque([(0,0)]) # 頂点0, 距離0
visited = [False]*N 

while dq:
    v,d = dq.pop()
    visited[v] = True
    cnt = 0 # 子がいくつあるか
    for e in A[v]:
        if visited[e]:
            continue
        cnt += 1
        dq.append((e, d+1))
    # 子がなければ何もしない
    if cnt==0:
        continue
    # 根の場合は, 根の1色以外を子に割り当て可能
    if d==0:
        n = Modinv.nPr(K-1,cnt)
    # それ以外の場合は, 親と自身の2色以外を子に割り当て可能
    else:
        n = Modinv.nPr(K-2,cnt)
    
    ans *= n
    ans %= mod

print(ans)

import sys
sys.setrecursionlimit(10**6)
MOD=10**9+7
def facinv(N):
    fac,finv,inv=[0]*(N+1),[0]*(N+1),[0]*(N+1)
    fac[0]=1;fac[1]=1;finv[0]=1;finv[1]=1;inv[1]=1
    for i in range(2,N+1):
        fac[i]=fac[i-1]*i%MOD
        inv[i]=MOD-inv[MOD%i]*(MOD//i)%MOD
        finv[i]=finv[i-1]*inv[i]%MOD
    return fac,finv,inv

def COM(n,r):
    if n<r or r<0:
        return 0
    else:
        return ((fac[n]*finv[r])%MOD*finv[n-r])%MOD

def dfs(v,p,dep):
    nonlocal res
    c=0
    for nv in G[v]:
        if nv==p:
            continue
        dfs(nv,v,dep+1)
        c+=1
    if dep==0:
        res=((res*COM(K-1,c)%MOD)*fac[c])%MOD
    else:
        res=((res*COM(K-2,c)%MOD)*fac[c])%MOD
    
N,K=map(int,input().split())
G=[[] for i in range(N)]
for i in range(N-1):
    a,b=map(lambda x:int(x)-1,input().split())
    G[a].append(b)
    G[b].append(a)
fac,finv,inv=facinv(max(K,N))
res=K
dfs(0,-1,0)
print(res%MOD)

import sys
sys.setrecursionlimit(1000000000)
n,k = map(int,input().split())
G = [[] for _ in range(n)]
for _ in range(n-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)

mod = 1000000007
def perm(n,k):
    if n < k: return 0
    if n < 0 or k < 0: return 0
    return fac[n]*finv[n-k]%mod
fac = [1]*(k+1)
finv = [1]*(k+1)
for i in range(1,k+1):
    fac[i] = fac[i-1]*i%mod
    finv[i] = pow(fac[i],mod-2,mod)

def dfs(cur,prev=-1):
    nxtcnt = 0
    res = 1
    for nxt in G[cur]:
        if nxt == prev: continue
        nxtcnt += 1
        res = res*dfs(nxt,cur)%mod
    colors = k-1 if cur == 0 else k-2
    res = res*perm(colors,nxtcnt)%mod
    return res
  
ans = k*dfs(0)%mod
print(ans)

import networkx as nx

def factorial(n, mod):
    fac = [0] * (n + 1)
    inv = [0] * (n + 1)
    fac[0], inv[0] = 1, 1
    for i in range(1, n + 1):
        fac[i] = fac[i-1] * i % mod
        inv[i] = inverse(fac[i], mod)
    return fac, inv

def inverse(a, mod):
    a %= mod # 除数が正なら正になる
    p = mod
    x, y = 0, 1
    while a > 0:
        n = p // a
        p, a = a, p % a, 
        x, y = y, x - n * y
    return x % mod # 除数が正なら正になる

mod = 1000000007

n, k = list(map(int, input().split()))
graph = nx.Graph()
graph.add_nodes_from(list(range(n)))

graph.add_edges_from([tuple([int(x) - 1 for x in input().split()]) for _ in range(n-1)])
if nx.degree(graph)[0] + 1 > k:
    print((0))
    return

fac, inv = factorial(k, mod)
ans = fac[k] * inv[k - nx.degree(graph)[0] - 1] % mod # nx.degree(graph)[0]:グラフの頂点0から出ている枝の数
for parent, child in nx.dfs_edges(graph, 0): # nx.dfs_edges(graph, 0):グラフの頂点0からDFS
    m = nx.degree(graph)[child]
    if m + 1 > k:
        print((0))
        return
    ans = ans * fac[k-2] % mod * inv[k-1-m] % mod
print(ans)


import sys
sys.setrecursionlimit(100000)

MOD = 10**9 + 7
N, K = map(int,input().split())

G = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int,input().split())
    a, b = a-1, b-1

    G[a].append(b)
    G[b].append(a)

# 頂点nowを根とする部分木の色の塗り方 (parが親の時)
#   ただしnowはすでに塗られているとする
def dfs(now, par):
    if K < len(G[now]): return 0

    res = 1

    if par == -1:
        colors = K-1
        for i in range(len(G[now])):
            res *= colors-i
            res %= MOD
    else:
        colors = K-2
        for i in range(len(G[now])-1):
            res *= colors-i
            res %= MOD

    for c in G[now]:
        if c == par: continue
        
        res *= dfs(c, now)
        res %= MOD
    
    return res

print(K * dfs(0,-1) % MOD)

from collections import deque

def main():
  N,K=map(int,input().split())
  mod = 10**9+7
  G=[[] for _ in range(N)]
  for i in range(N-1):
    a,b=map(int,input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)

  def bfs(s):
      seen = [0]*N
      color = [0]*N
      todo = deque()
      seen[s]=1
      todo.append(s)
      color[s]=K
      while todo:
        a = todo.popleft()
        if a == s: count = K-1
        else: count = K-2
        for b in G[a]:
          if seen[b] == 0:
            seen[b] = 1
            todo.append(b)
            color[b] = count %mod
            count -= 1
      return color

  MAX,start = 0,-1
  for i in range(N):
    if len(G[i])>MAX:
      MAX=len(G[i])
      start = i
  
  color = bfs(start)
  ans = 1
  for i in range(N):
    ans *= color[i]
    ans %= mod

  print(ans)
  
def __starting_point():
  main()
__starting_point()

import networkx as nx

def factorial(n, mod):
    fac = [0] * (n + 1)
    inv = [0] * (n + 1)
    fac[0], inv[0] = 1, 1
    for i in range(1, n + 1):
        fac[i] = fac[i-1] * i % mod
        inv[i] = inverse(fac[i], mod)
    return fac, inv

def inverse(a, mod):
    a %= mod # 除数が正なら正になる
    p = mod
    x, y = 0, 1
    while a > 0:
        n = p // a
        p, a = a, p % a, 
        x, y = y, x - n * y
    return x % mod # 除数が正なら正になる

mod = 1000000007

n, k = list(map(int, input().split()))
graph = nx.Graph()
graph.add_nodes_from(list(range(n)))
for _ in range(n-1):
    a, b = [int(x) - 1 for x in input().split()]
    graph.add_edge(a, b)
if nx.degree(graph)[0] + 1 > k:
    print((0))
    return

fac, inv = factorial(k, mod)
ans = fac[k] * inv[k - nx.degree(graph)[0] - 1] % mod # nx.degree(graph)[0]:グラフの頂点0から出ている枝の数
for parent, child in nx.dfs_edges(graph, 0): # nx.dfs_edges(graph, 0):グラフの頂点0からDFS
    m = nx.degree(graph)[child]
    if m + 1 > k:
        print((0))
        return
    ans = ans * fac[k-2] % mod * inv[k-1-m] % mod
print(ans)


import sys
sys.setrecursionlimit(10**6)
MOD=10**9+7
def facinv(N):
    fac,finv,inv=[0]*(N+1),[0]*(N+1),[0]*(N+1)
    fac[0]=1;fac[1]=1;finv[0]=1;finv[1]=1;inv[1]=1
    for i in range(2,N+1):
        fac[i]=fac[i-1]*i%MOD
        inv[i]=MOD-inv[MOD%i]*(MOD//i)%MOD
        finv[i]=finv[i-1]*inv[i]%MOD
    return fac,finv,inv

def PER(n,r):
    if n<r or r<0:
        return 0
    else:
        return (fac[n]*finv[n-r])

def dfs(v,p,dep):
    nonlocal res
    c=0
    for nv in G[v]:
        if nv==p:
            continue
        dfs(nv,v,dep+1)
        c+=1
    if dep==0:
        res=(res*PER(K-1,c)%MOD)
    else:
        res=(res*PER(K-2,c)%MOD)
    
N,K=map(int,input().split())
G=[[] for i in range(N)]
for i in range(N-1):
    a,b=map(lambda x:int(x)-1,input().split())
    G[a].append(b)
    G[b].append(a)
fac,finv,inv=facinv(max(K,N))
res=K
dfs(0,-1,0)
print(res%MOD)

import sys
sys.setrecursionlimit(10**9)
N,K = map(int,input().split())
edges = [[] for _ in range(N)]
used = [False]*N
mod = 10**9+7
for _ in range(N-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    edges[a].append(b)
    edges[b].append(a)
def f(n,c):
    sm = 1
    t = K-c
    for m in edges[n]:
        if not used[m]:
            used[m] = True
            if t <= 0:
                print(0)
                return
            sm = (sm*f(m,2)*t) % mod
            t -= 1
    return sm
used[0] = True
print(K*f(0,1) % mod)

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
fac = [-1] * (10**6+1)
inv = [-1] * (10**6+1)
finv = [-1] * (10**6+1)

fac[0] = fac[1] = 1
inv[1] = 1
finv[0] = finv[1] = 1

def initNCMMod(limit):
    for i in range(2, limit):
        fac[i] = fac[i-1] * i % mod
        inv[i] = mod - inv[mod%i] * (mod // i) % mod
        finv[i] = finv[i-1] * inv[i] % mod

def NCMMod(n, k):
    if n < k:
        return 0
    if (n < 0 or k < 0):
        return 0
    return fac[n] * (finv[k] * finv[n-k] % mod) % mod
initNCMMod(10**5+1)

def P(n, k):
    return (fac[n] * finv[n-k]) % mod

def main():
    N, K = LI()
    G = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b = LI_()
        G[a].append(b)
        G[b].append(a)
    q = deque([])
    q.append((0, -1, True))
    ans = K
    while q:
        v, par, is_root = q.popleft()
        n_child = len(G[v])
        remain_color = K - 1

        if not is_root:
            remain_color -= 1
            n_child -= 1

        for next_v in G[v]:
            if next_v == par:
                continue
            q.append((next_v, v, False))

        if n_child <= remain_color:
            ans *= P(remain_color, n_child)
            ans %= mod
        else:
            ans = 0
            break

    print(ans)

main()



import sys
sys.setrecursionlimit(10**5)

n,k=map(int,input().split())
m=10**9+7
to=[[] for i in range(n)]
for i in range(n-1):
  a,b=map(lambda x:int(x)-1, input().split())
  to[a].append(b)
  to[b].append(a)
frac=[1]*(10**5+1)
for i in range(1,10**5+1):
  frac[i]=frac[i-1]*i
  frac[i]%=m


def nPk(_n,_k):
  if _n<0 or _k<0 or _n-_k<0: return 0;
  a=frac[_n]
  b=frac[_n-_k]
  return (a*pow(b,m-2,m))%m


def dfs(_v, _u=-1):
  nonlocal ans
  for u in to[_v]:
    if u==_u: continue
    dfs(u, _v)
  p=len(to[_v])
  ans*=nPk(k,p+1) if _v==0 else nPk(k-2,p-1)
  ans%=m
    
    
ans=1
chk=[False]*n
dfs(0)
  
print(ans)

import sys
sys.setrecursionlimit(10 ** 6)
N, K = map(int, input().split())
mod = 10 ** 9 + 7
edges = [[] for _ in range(N)]
for _ in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    edges[a].append(b)
    edges[b].append(a)


def dfs(K, u, p):
    if p == -1:
        can_use_color_num = K - 1
    else:
        can_use_color_num = K - 2

    # if K < len(edges[u]):
    #     return 0
    # else:
    case_num = 1
    for e in edges[u]:
        if e == p:
            continue
        case_num *= can_use_color_num
        can_use_color_num -= 1
        case_num %= mod
    for e in edges[u]:
        if e == p:
            continue
        case_num *= dfs(K, e, u)
        case_num %= mod
    return case_num

ans = K * dfs(K, 0, -1)
ans %= mod
print(ans)