Given a [tree] containing N nodes.

Each node can be coloured using exactly one of the C colours. Find the number of colourings of the tree such that:
All nodes in a path of length at most two have distinct colours.

As the answer can be huge, print it modulo (10 ^ 9 + 7).

Note:
Two colourings of a tree are different if there exists at least one node having different colours in both the colourings.
A path in a tree is a sequence of (zero or more) connected nodes.
The path length between two nodes is defined as the total number of edges in the shortest path from one node to other.

------ Input Format ------ 

- The first line of the input will contain two integers N and C, the number of nodes in the tree and the number of colours available respectively. 
- The next (N - 1) lines will describe the given tree. Each line contains two integers U and V meaning that there is an edge between node U and node V.

------ Output Format ------ 

- Output the number of ways to colour the tree satisfying the given condition, modulo 10^{9} + 7.

------ Constraints ------ 

$ 1 ≤ N ≤ 10^{6}$ 
$ 1 ≤ C ≤ 10^{6}$ 
$ 1 ≤ U, V ≤ N$ 

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

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

----- explanation 1 ------ 
The valid colourings of nodes $1, 2,$ and $3$ are: $\{1, 2, 3\}, \{1, 3, 2\}, \{2, 1, 3\}, \{2, 3, 1\}, \{3, 1, 2\},$ and $\{3, 2, 1\}$.

Paths having length at most $2$ are: $1 - 2, 1 - 3,$ and $2 - 1 - 3$. Note that for any valid colouring, all the nodes in each of these paths have distinct colours.

Difficulty: MEDIUM_HARD
Tags: Graph algorithms

Graph traversal

Combinatorics

Tree algorithms

Mathematics

Data structures
Skill types: Data structures

Starter code:

Solutions:
(n, c) = map(int, input().split())
d = dict()
checker = [False for i in range(n)]
for i in range(n - 1):
	t = tuple(map(int, input().split()))
	if not checker[t[0] - 1]:
		checker[t[0] - 1] = True
		d[t[0]] = list()
	d[t[0]].append(t[1])
	if not checker[t[1] - 1]:
		checker[t[1] - 1] = True
		d[t[1]] = list()
	d[t[1]].append(t[0])
if c == 1:
	if n == 1:
		print(1)
	else:
		print(0)
else:
	val = 0
	for i in range(n):
		val = max(val, len(d[i + 1]))
	if val + 1 > c:
		print(0)
	else:
		re = c
		q = 1
		checker[0] = False
		new_c = list()
		for e in d[1]:
			new_c.append(e)
			checker[e - 1] = False
			q += 1
		for i in range(len(d[1])):
			re = re * (c - 1 - i) % (10 ** 9 + 7)
		while q < n:
			new_new_c = list()
			for e in new_c:
				for ee in d[e]:
					if checker[ee - 1]:
						new_new_c.append(ee)
						checker[ee - 1] = False
						q += 1
				for i in range(len(d[e]) - 1):
					re = re * (c - 2 - i) % (10 ** 9 + 7)
			new_c = new_new_c.copy()
		print(re)


from typing import List
TRUNCATOR = 10 ** 9 + 7

def main(nodes_num: int, colors_num: int, edges: List[List[int]]) -> int:
	if nodes_num == 1:
		return colors_num
	adjacency_lists: List[List[int]] = [[] for _ in range(nodes_num)]
	for (u, v) in edges:
		adjacency_lists[u - 1].append(v - 1)
		adjacency_lists[v - 1].append(u - 1)
	required_colors_num = 1 + len(max(adjacency_lists, key=lambda x: len(x)))
	if colors_num < required_colors_num:
		return 0
	dfs_stack = []
	node_is_visited = [False] * nodes_num
	res = 1
	for node_idx in range(nodes_num):
		if len(adjacency_lists[node_idx]) == 1:
			dfs_stack.append(adjacency_lists[node_idx][0])
			node_is_visited[dfs_stack[0]] = True
			break
	while dfs_stack:
		node_idx = dfs_stack.pop()
		used_nodes_num = 1 if node_is_visited[node_idx] and res != 1 else 0
		for adjacent_idx in adjacency_lists[node_idx]:
			if node_is_visited[adjacent_idx]:
				used_nodes_num += 1
			elif len(adjacency_lists[adjacent_idx]) > 1:
				dfs_stack.append(adjacent_idx)
				node_is_visited[adjacent_idx] = True
		numerator = colors_num - used_nodes_num
		denominator = colors_num - len(adjacency_lists[node_idx]) - 1
		for multiplier in range(denominator + 1, numerator + 1):
			res = res * multiplier % TRUNCATOR
	return res
(nodes_n, colors_n) = [int(num) for num in input().split()]
edges = [[int(num) for num in input().split()] for _ in range(nodes_n - 1)]
print(main(nodes_n, colors_n, edges))


import sys
M = 10 ** 9 + 7
i = (map(int, s.split()) for s in sys.stdin)
(n, c) = next(i)
g = [None] + [[] for _ in range(n)]
V = [None, True] + [False] * (n - 1)
for (u, v) in i:
	g[u].append(v)
	g[v].append(u)
fact = [1] * c
for i in range(1, c):
	fact[i] = fact[i - 1] * i % M
r = c
st = [1]
while st:
	u = st.pop()
	f = u > 1
	k = c - 1 - f
	m = len(g[u]) - f
	if m > k:
		r = 0
		break
	r = r * fact[k] * pow(fact[k - m], M - 2, M) % M
	for v in g[u]:
		if not V[v]:
			V[v] = True
			st.append(v)
print(r)


import sys
sys.setrecursionlimit(10 ** 6)
(n, c) = map(int, input().split())
tree = {}
child = [0] * (n + 1)
parent = {}
val = [0] * (n + 1)
mod = 10 ** 9 + 7
for i in range(1, n + 1):
	child[i] = 0
	tree[i] = []
	parent[i] = 0
for _ in range(n - 1):
	(a, b) = map(int, input().split())
	tree[a] += [b]
	tree[b] += [a]

def dfs(root, par):
	if val[root]:
		return
	x = 0
	if par == -1:
		val[root] = c
	else:
		x = child[par]
		if child[parent[par]]:
			val[root] = (c - x - 2) % mod
		else:
			val[root] = (c - x - 1) % mod
		child[par] += 1
	for node in tree[root]:
		if node != par:
			parent[node] = root
			dfs(node, root)
dfs(1, -1)
ans = 1
for i in range(1, len(val)):
	ans = ans * val[i] % mod
print(ans % mod)


import sys
sys.setrecursionlimit(10000000)
from collections import defaultdict as dd
MOD = 10 ** 9 + 7

def count(graph, c, d, cur, childnum, parent=None):
	result = c - min(d, 2) - childnum
	after_parent = False
	for (i, child) in enumerate(graph[cur]):
		if child == parent:
			after_parent = True
			continue
		result *= count(graph, c, d + 1, child, i - after_parent, cur)
		result %= MOD
	return result % MOD

def main():
	(n, c) = map(int, input().split())
	graph = dd(list)
	for _ in range(n - 1):
		(a, b) = map(int, input().split())
		graph[a].append(b)
		graph[b].append(a)
	degrees = dd(int)
	for i in range(1, n + 1):
		degrees[len(graph[i])] += 1
	if n == 1:
		print(c)
		return
	result = c * (c - 1)
	for (d, cnt) in degrees.items():
		for x in range(2, d + 1):
			result *= pow(c - x, cnt, MOD)
			result %= MOD
	print(result)
main()


(n, c) = map(int, input().split())
l = [int(0) for x in range(n)]
for _ in range(n - 1):
	(u, v) = map(int, input().split())
	l[u - 1] = l[u - 1] + int(1)
l.sort()
l.reverse()
z = l[0]
v = l[1]
l.remove(z)
d = min(l)
n = l.index(d)
l = l[:n]
l2 = [1]
mul = 1
for i in range(v):
	mul = mul * (c - 2 - i)
	l2.append(mul)
max = 1
for k in range(z + 1):
	max = max * (c - k) % (10 ** 9 + 7)
for j in l:
	max = max * l2[j] % (10 ** 9 + 7)
print(max % (10 ** 9 + 7))


mod = 10 ** 9 + 7
(n, c) = map(int, input().split())
graph = [[] for _ in range(n + 1)]
for _ in range(n - 1):
	(a, b) = map(int, input().split())
	graph[a].append(b)
	graph[b].append(a)
ans = 1
vis = [0] * (n + 1)
queue = [(1, 0)]
while queue:
	(node, nearby) = queue.pop()
	ans = ans * (c - nearby) % mod
	(vis[node], nearby) = (1, 1)
	for i in graph[node]:
		if not vis[i]:
			queue.append((i, nearby))
		nearby += 1
print(ans)


from collections import defaultdict
mod = 1000000007
(n, c) = map(int, input().split())
dic = defaultdict(int)
for i in range(n - 1):
	(u, v) = map(int, input().split())
	dic[u] += 1
ans = c
seclayer = True
for el in dic:
	if seclayer:
		k = c - 1
		for i in range(dic[el]):
			ans = ans * k % mod
			k -= 1
		seclayer = False
	else:
		k = c - 2
		for i in range(dic[el]):
			ans = ans * k % mod
			k -= 1
ans %= mod
print(ans)


def build_graph(connections):
	graph = {}
	for (n1, n2) in connections:
		if n1 in graph:
			graph[n1].add(n2)
		else:
			graph[n1] = set([n2])
		if n2 in graph:
			graph[n2].add(n1)
		else:
			graph[n2] = set([n1])
	for k in graph:
		graph[k] = list(graph[k])
	return graph

def f(connections, c):
	graph = build_graph(connections)
	diffs = {}
	for k in graph:
		diffs[k] = 0
	mod = 10 ** 9 + 7
	visited = set()
	frontier = []
	root = list(graph.keys())[0]
	res = c
	if len(graph[root]) == 0:
		return res
	visited.add(root)
	frontier_block = graph[root]
	frontier += frontier_block
	for i in range(len(frontier_block)):
		diffs[frontier_block[i]] = 1 + len(frontier_block) - 1 - i
	k = frontier.pop()
	visited.add(k)
	if c == 1:
		return 0
	res *= c - 1
	if len(graph[root]) == 1 and len(graph[k]) == 1:
		return res
	frontier_block = list(set(graph[k]) - visited)
	frontier += frontier_block
	for i in range(len(frontier_block)):
		diffs[frontier_block[i]] = 2 + len(frontier_block) - 1 - i
	while len(frontier) > 0:
		k = frontier.pop()
		visited.add(k)
		if c <= diffs[k]:
			return 0
		res = res * (c - diffs[k]) % mod
		frontier_block = list(set(graph[k]) - visited)
		frontier += frontier_block
		for i in range(len(frontier_block)):
			diffs[frontier_block[i]] = 2 + len(frontier_block) - 1 - i
	return res
(n, c) = [int(el) for el in input().split(' ')]
connections = []
for i in range(n - 1):
	(n1, n2) = [int(el) for el in input().split(' ')]
	connections.append((n1, n2))
print(f(connections, c))


from collections import defaultdict

def solve(t):
	(n, c) = map(int, input().split())
	d = defaultdict(int)
	mod = 1000000007
	for _ in range(n - 1):
		(x, y) = map(int, input().split())
		d[x] += 1
	ans = c
	county = 1
	for ele in d:
		if county == 1:
			k = c - 1
			for _ in range(d[ele]):
				ans *= k
				ans %= mod
				k -= 1
			county += 1
		else:
			k = c - 2
			for _ in range(d[ele]):
				ans *= k
				ans %= mod
				k -= 1
	return ans
t = 1
print(solve(t))


from bisect import bisect_left
from bisect import bisect_right
from getopt import getopt
from re import sub
import re
from typing import DefaultDict
import math
from collections import defaultdict
from math import sqrt
import collections
from sys import maxsize
from itertools import combinations_with_replacement
import sys
import copy
import heapq
from collections import deque

def sieve_erasthones(n):
	cnt = 0
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p ** 2, n + 1, p):
				prime[i] = False
		p += 1
	prime[0] = False
	prime[1] = False
	return prime

def calculate(p, q):
	mod = 998244353
	expo = 0
	expo = mod - 2
	while expo:
		if expo & 1:
			p = p * q % mod
		q = q * q % mod
		expo >>= 1
	return p

def count_factors(n):
	i = 1
	c = 0
	ans = []
	while i <= math.sqrt(n):
		if n % i == 0:
			if n // i == i:
				c += 1
				ans.append(n // i)
			else:
				c += 2
				ans.append(i)
				ans.append(n // i)
		i += 1
	return ans

def ncr_modulo(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def isprime(n):
	prime_flag = 0
	if n > 1:
		for i in range(2, int(sqrt(n)) + 1):
			if n % i == 0:
				prime_flag = 1
				break
		if prime_flag == 0:
			return True
		else:
			return False
	else:
		return True

def smallestDivisor(n):
	if n % 2 == 0:
		return 2
	i = 3
	while i * i <= n:
		if n % i == 0:
			return i
		i += 2
	return n

def dict_ele_count(l):
	d = defaultdict(lambda : 0)
	for ele in l:
		d[ele] += 1
	return d

def max_in_dict(d):
	maxi = 0
	for ele in d:
		if d[ele] > maxi:
			maxi = d[ele]
	return maxi

def element_count(s):
	l = []
	k = s[0]
	c = 0
	for ele in s:
		if ele == k:
			c += 1
		else:
			l.append([k, c])
			k = ele
			c = 1
	l.append([k, c])
	return l

def modular_exponentiation(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 != 0:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def number_of_primefactor(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(i)
			n = n / i
	if n > 2:
		l.append(n)
	return list(set(l))

def twosum(a, n, x):
	rem = []
	for i in range(x):
		rem.append(0)
	for i in range(n):
		if a[i] < x:
			rem[a[i] % x] += 1
	for i in range(1, x // 2):
		if rem[i] > 0 and rem[x - i] > 0:
			return True
	if i >= x // 2:
		if x % 2 == 0:
			if rem[x // 2] > 1:
				return True
			else:
				return False
		elif rem[x // 2] > 0 and rem[x - x // 2] > 0:
			return True
		else:
			return False

def divSum(num):
	result = 0
	i = 2
	while i <= math.sqrt(num):
		if num % i == 0:
			if i == num / i:
				result = result + i
			else:
				result = result + (i + num / i)
		i = i + 1
	return result + 1 + num

def subsequence(str1, str2):
	m = len(str1)
	n = len(str2)
	j = 0
	i = 0
	while j < m and i < n:
		if str1[j] == str2[i]:
			j = j + 1
		i = i + 1
	return j == m

def primeFactors(n):
	d = defaultdict(lambda : 0)
	while n % 2 == 0:
		d[2] += 1
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			d[int(i)] += 1
			n = n / i
	if n > 2:
		d[int(n)] += 1
	return d

def modInverse(b, m):
	g = math.gcd(b, m)
	if g != 1:
		return -1
	else:
		return pow(b, m - 2, m)

def modDivide(a, b, m):
	a = a % m
	inv = modInverse(b, m)
	return inv * a % m

def count(n):
	ans = 0
	while n:
		ans += n % 10
		n //= 10
	return ans

def lcm(a, b):
	return a * b // math.gcd(a, b)

def check(n):
	c = 0
	while n % 2 == 0:
		n //= 2
		c += 1
	return c

def modInverse(b, m):
	return pow(b, m - 2, m)

def modDivide(a, b, m):
	a = a % m
	inv = modInverse(b, m)
	return inv * a % m

def lisToStr(s):
	str1 = ''
	for ele in s:
		str1 += ele
	return str1

def listy(l):
	ans = []
	for i in range(len(l)):
		ans.append(heapq.heappop(l))
	return ans

def getOdd(n):
	for i in range(1, 33, 2):
		if 2 ** i > n:
			return 2 ** (i - 2)

def pali(s, i, j):
	while i <= j:
		if s[i] == s[j]:
			i += 1
			j -= 1
		else:
			return False
	return True

def solve(t):
	(n, c) = map(int, input().split())
	d = defaultdict(lambda : 0)
	mod = 1000000007
	for _ in range(n - 1):
		(x, y) = map(int, input().split())
		d[x] += 1
	ans = c
	county = 1
	for ele in d:
		if county == 1:
			k = c - 1
			for _ in range(d[ele]):
				ans *= k
				ans %= mod
				k -= 1
			county += 1
		else:
			k = c - 2
			for _ in range(d[ele]):
				ans *= k
				ans %= mod
				k -= 1
	return ans
t = 1
print(solve(t))


import collections, math, bisect, sys
from collections import OrderedDict, Counter, defaultdict
from sys import stdin, stdout

def get_line():
	return list(map(int, sys.stdin.readline().strip().split()))

def in1():
	return int(stdin.readline())

def display_arr(arr):
	stdout.write(' '.join(map(str, arr)) + '\n')

def display_num(num):
	stdout.write(str(num) + '\n')

def factorial(n):
	return n * factorial(n - 1) if n > 1 else 1

def fact(n):
	n = n - 1
	return n * (n + 1) // 2

def lcm(x, y):
	return x * y // math.gcd(x, y)
a = []

def SieveOfEratosthenes(n):
	prime = [True] * (n + 1)
	p = 2
	while p * p <= n:
		print(p)
		if prime[p]:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	a = []
	for p in range(2, n + 1):
		if prime[p]:
			a.append(p)

def add(i):
	return (1 << i) - 1

def rsb(k):
	p = 1
	while k > 0:
		if k & 1:
			return p - 1
		p += 1
		k = k >> 1

def phone_number(s):
	ans = ''
	l = 0
	mul = 1
	for i in range(len(s)):
		if s[i] == ' ':
			r = i
			char = s[l:r]
			if char == 'double':
				mul = 2
			elif char == 'triple':
				mul = 3
			else:
				ans += mul * d[char]
				mul = 1
			l = r + 1
	ans += mul * str(d[s[l:len(s)]])
	return ans

def reverseColumns(arr):
	(arr[0][0], arr[3][0]) = (arr[3][0], arr[0][0])
	(arr[0][1], arr[3][1]) = (arr[3][1], arr[0][1])
	(arr[0][2], arr[3][2]) = (arr[3][2], arr[0][2])
	(arr[0][3], arr[3][3]) = (arr[3][3], arr[0][3])
	(arr[1][0], arr[2][0]) = (arr[2][0], arr[1][0])
	(arr[1][3], arr[2][3]) = (arr[2][3], arr[1][3])
	(arr[1][1], arr[2][1]) = (arr[2][1], arr[1][1])
	(arr[1][2], arr[2][2]) = (arr[2][2], arr[1][2])
	return arr

def transpose(arr):
	R = C = 4
	for i in range(R):
		for j in range(i, C):
			t = arr[i][j]
			arr[i][j] = arr[j][i]
			arr[j][i] = t
	return arr

def isPrime(n):
	if n == 1:
		return 0
	i = 2
	while i * i <= n:
		if n % i == 0:
			return 0
		i += 1
	return 1

def give_matrix(e):
	temp = []
	me = []
	for i in range(16):
		temp.append(ord(e[i]))
	me.append(temp[0:4])
	me.append(temp[4:8])
	me.append(temp[8:12])
	me.append(temp[12:16])
	return me

def XOR(m1, m2):
	for i in range(len(m1)):
		for j in range(len(m2)):
			m1[i][j] = m1[i][j] ^ m2[i][j]
	return m1

def x_4(m1):
	for i in range(len(m1)):
		for j in range(len(m1)):
			m1[i][j] = m1[i][j] ^ 4
	return m1

def isFeasible(a, k, ans):
	n = len(a)
	res = sum = i = 0
	res = 1
	while i < n:
		sum += a[i]
		if sum > ans:
			res += 1
			sum = a[i]
		i += 1
	if res <= k:
		return 1
	return 0

def binary_search(a, l, r):
	while l <= r:
		m = (l + r) // 2
		if isFeasible(a, k, m):
			r = m - 1
		else:
			l = m + 1
	return l

def isCollinear(a, b, c):
	(x1, y1) = a
	(x2, y2) = b
	(x3, y3) = c
	a = x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2)
	if a == 0:
		return 1
	return 0

def rec(a, n, p):
	if n <= -1:
		return 0
	(no_take2, no_take1, take1, take2, no_take_even, no_take_odd) = (0, 0, 0, 0, 0, 0)
	if p:
		if a[n] & 1:
			take1 += a[n] + rec(a, n - 1, ~p)
		else:
			no_take1 += rec(a, n - 1, ~p)
	elif a[n] % 2 == 0:
		take2 += a[n] + rec(a, n - 1, ~p)
	else:
		no_take2 += rec(a, n - 1, ~p)
	return max(no_take2, no_take1, take1, take2, no_take_even, no_take_odd)

def digitSum(x):
	sum = 0
	while x:
		sum += x % 10
		x //= 10
	return sum
import string
a = []
for l in string.ascii_lowercase:
	a.append(l)
from functools import lru_cache

def removeInvalidParentheses(s):

	def dfs(s):
		mi = calc(s)
		if mi == 0:
			return [s]
		ans = []
		for x in range(len(s)):
			if s[x] in ('(', ')'):
				ns = s[:x] + s[x + 1:]
				if ns not in visited and calc(ns) < mi:
					visited.add(ns)
					ans.extend(dfs(ns))
		return ans

	def calc(s):
		a = b = 0
		for c in s:
			a += {'(': 1, ')': -1}.get(c, 0)
			b += a < 0
			a = max(a, 0)
		return a + b
	visited = set([s])
	return dfs(s)

def countAllBits(A):
	ans = 0
	a = [0] * 32
	for bit in range(32):
		for n in A:
			if n & 1 << bit:
				a[bit] = 1
				ans += 1
	return sum(a)

def diff(a, b):
	ans = 0
	for i in range(len(a)):
		ans += abs(a[i] - b[i])
	return ans
num = ('0', '1', '2', '3', '4', '5', '6', '7', '8', '9')
(cap, smal) = (set(), set())
for letter in string.ascii_uppercase:
	cap.add(letter)
for letter in string.ascii_lowercase:
	smal.add(letter)
spe = ('#', '@', '*', '&')
d = {}

def dp(n, t):
	if n == 1:
		dp[n, t] = 1
		return dp[n, t]
	if n in (2, 3):
		return dp[n, t]
	if (n, t) in d:
		return d[n, t]
	else:
		(p1, p2, p3) = (float('inf'), float('inf'), float('inf'))
		if t == 1:
			p1 = min(dp(n - 2, 2), dp(n - 3, 3))
		elif t == 2:
			p2 = min(dp(n - 1, 1), dp(n - 3, 3))
		else:
			p3 = min(dp(n - 2, 2), dp(n - 1, 1))
		d[n, t] = 1 + min(p1, p2, p3)
		return d[n, t]

def removeReverse(S):
	res = []
	d = set()
	c = 0
	for i in S:
		if i not in d:
			d.add(i)
			res.append(i)
		else:
			c += 1
	print(c, res)
	if c & 1:
		res = res[::-1]
	return ''.join(res)
a = [1, 2, 4, 5, 7, 8, 10, 11, 13, 14, 16]
b = [2, 3, 5, 6, 8, 9, 11, 12, 14, 15, 17]
c = [3, 4, 6, 7, 9, 10, 12, 13, 15, 16]
d = [4, 5, 7, 8, 10, 11, 13, 14, 16]
e = [5, 6, 8, 9, 11, 12, 14, 15, 17]
f = [6, 7, 9, 10, 12, 13, 15, 16, 18]

def percent(x, p):
	return x * p / 100

def maximalSquare(A) -> int:
	(m, n) = (len(A), len(A[0]))
	dp = [[0 for i in range(n + 1)] for i in range(m + 1)]
	ans = 0
	for i in range(m):
		for j in range(n):
			if A[i][j] == 1:
				dp[i + 1][j + 1] = 1 + min(dp[i + 1][j], dp[i][j], dp[i][j + 1])
				ans = max(ans, dp[i + 1][j + 1])
	return ans

def isPali(s):
	(l, r) = (0, len(s) - 1)
	while l < r:
		if s[l] != s[r]:
			return 0
		(l, r) = (l + 1, r - 1)
	return s

def main():

	def solve():
		f = a[n - 1]
		if f == 0:
			return 'NO'
		s = a[f - 1]
		if s == 0:
			return 'NO'
		return 'YES'
	(n, c) = get_line()
	mod = 1000000007
	graph = [[] for i in range(n + 1)]
	for _ in range(n - 1):
		(a, b) = get_line()
		graph[a].append(b)
		graph[b].append(a)
	seen = set()
	q = [(1, 0)]
	ans = 1
	while q:
		(node, nearby) = q.pop()
		ans = ans * (c - nearby) % mod
		seen.add(node)
		nearby = 1
		for i in graph[node]:
			if i not in seen:
				q.append((i, nearby))
			nearby += 1
	print(ans)
main()


(n, c) = input().split()
(n, c) = (int(n), int(c))
arr = []
for i in range(n - 1):
	pair = input().split()
	arr.append([int(pair[0]), int(pair[1])])
if n == 1:
	print(c)
else:
	mp = {}
	for i in range(n - 1):
		pair = arr[i]
		v1 = pair[0]
		v2 = pair[1]
		if v1 not in mp:
			mp[v1] = [v2]
		else:
			mp[v1].append(v2)
		if v2 not in mp:
			mp[v2] = [v1]
		else:
			mp[v2].append(v1)
	memo = {}
	mod = 10 ** 9 + 7
	val = arr[0][0]
	cur_layer = 1
	cnt = 1
	layer = []
	brks = []
	flag = True
	while True:
		if flag == False:
			break
		if cur_layer == 1:
			cnt = cnt * c % mod
			for i in range(len(mp[val])):
				layer.append(mp[val][i])
			cur_layer += 1
			memo[val] = True
			continue
		if cur_layer == 2:
			prev_nodes = 0
			for i in range(len(layer)):
				if c - 1 - prev_nodes <= 0:
					flag = False
				cnt = cnt * (c - 1 - prev_nodes) % mod
				prev_nodes += 1
			new_layer = []
			new_brks = []
			for i in range(len(layer)):
				if len(new_brks) == 0:
					new_brks.append(len(mp[layer[i]]) - 1)
				else:
					new_brks.append(new_brks[len(new_brks) - 1] + len(mp[layer[i]]) - 1)
				memo[layer[i]] = True
				for j in range(len(mp[layer[i]])):
					if mp[layer[i]][j] in memo:
						continue
					new_layer.append(mp[layer[i]][j])
			cur_layer += 1
			layer = new_layer
			brks = new_brks
			if len(new_layer) == 0:
				break
			continue
		prev_nodes = 0
		pt = 0
		for i in range(len(layer)):
			if i == brks[pt]:
				prev_nodes = 0
				pt += 1
			if c - 2 - prev_nodes <= 0:
				flag = False
			cnt = cnt * (c - 2 - prev_nodes) % mod
			prev_nodes += 1
		new_layer = []
		new_brks = []
		for i in range(len(layer)):
			if len(new_brks) == 0:
				new_brks.append(len(mp[layer[i]]) - 1)
			else:
				new_brks.append(new_brks[len(new_brks) - 1] + len(mp[layer[i]]) - 1)
			memo[layer[i]] = True
			for j in range(len(mp[layer[i]])):
				if mp[layer[i]][j] in memo:
					continue
				new_layer.append(mp[layer[i]][j])
		cur_layer += 1
		layer = new_layer
		brks = new_brks
		if len(new_layer) == 0:
			break
		continue
	if flag == False:
		print(0)
	else:
		print(cnt)


from collections import defaultdict
import sys

def dfs(root, parent, graph, ways, c, child_colored):
	if parent == -1:
		ways[root] = c
	elif parent == 0:
		ways[root] = max(c - 1 - child_colored[parent], 0)
	else:
		ways[root] = max(c - 1 - child_colored[parent] - 1, 0)
	for child in graph[root]:
		if child != parent:
			dfs(child, root, graph, ways, c, child_colored)
			child_colored[root] += 1
sys.setrecursionlimit(10 ** 6)
mod = 10 ** 9 + 7
(n, c) = [int(x) for x in input().split()]
graph = defaultdict(list)
for i in range(n - 1):
	(u, v) = [int(x) for x in input().split()]
	graph[u - 1].append(v - 1)
	graph[v - 1].append(u - 1)
child_colored = defaultdict(int)
ways = [0] * n
dfs(0, -1, graph, ways, c, child_colored)
ans = 1
for way in ways:
	ans = ans * way % mod
print(ans)


import sys
sys.setrecursionlimit(10 ** 6)
(n, c) = map(int, input().split())
gr = [[] for i in range(n)]
for i in range(n - 1):
	(x, y) = map(int, input().split())
	gr[x - 1].append(y - 1)
	gr[y - 1].append(x - 1)

def dfs(i, n, f, vis):
	if i in vis:
		return 1
	vis.add(i)
	ans = 1
	c = 1
	if f == 0:
		for j in gr[i]:
			if j not in vis:
				ans = ans * (n - c) * dfs(j, n, 1, vis)
				ans %= 10 ** 9 + 7
				c += 1
	else:
		c = 2
		for j in gr[i]:
			if j not in vis:
				ans = ans * (n - c) * dfs(j, n, 1, vis)
				c += 1
				ans %= 10 ** 9 + 7
	return ans
ans = c * dfs(0, c, 0, set())
ans %= 10 ** 9 + 7
print(ans)


ri = lambda : int(input())
rl = lambda : list(map(int, input().split()))
rs = lambda : input()
from collections import defaultdict
import sys
sys.setrecursionlimit(1000000)
M = 1000000007
ways = 0

def dfs(node, s, color):
	c = 0
	if not node:
		return
	if node not in parent:
		ways = color - s
	elif parent[node] not in parent:
		ways = color - s - 1
	else:
		ways = color - s - 2
	choices[node] = ways % M
	if node not in adj:
		return
	for x in adj[node]:
		dfs(x, c, color)
		c += 1

def calc():
	for i in adj:
		if i == root:
			f = c * find(c - 1, len(adj[i]))
			f %= M
			ways = ways + f
			ways %= M
		else:
			f = find(c - 2, len(adj[i]))
			f %= M
			ways = ways * f
			ways %= M

def find(n, r):
	if r > n:
		flag = 0
		return 0
	total = 1
	for i in range(n - r + 1, n + 1):
		total = total * i
		total %= M
	return total
(n, c) = rl()
adj = {}
parent = {}
choices = {}
for i in range(n - 1):
	(x, y) = map(int, input().split())
	if x not in adj:
		adj[x] = [y]
	else:
		adj[x].append(y)
	parent[y] = x
root = None
for x in adj:
	if x not in parent:
		root = x
		break
dfs(root, 0, c)
ans = 1
for x in choices:
	ans *= choices[x]
	ans %= M
print(ans)


from collections import defaultdict
import sys
sys.setrecursionlimit(10 ** 6)
mod = 10 ** 9 + 7

def dfs(node, par, x):
	v[node] = 1
	ans = x
	if par == -1:
		j = 1
	else:
		j = 2
	for i in adj[node]:
		if not v[i]:
			ans *= dfs(i, node, c - j)
			ans %= mod
			j += 1
	return ans
(n, c) = map(int, input().split())
adj = {i + 1: [] for i in range(n)}
for i in range(n - 1):
	(u, v) = map(int, input().split())
	adj[u].append(v)
	adj[v].append(u)
v = [0] * (n + 1)
fans = dfs(1, -1, c)
fans %= mod
print(fans)


import sys
from math import sqrt, gcd, factorial, ceil, floor, pi
from collections import deque, Counter, OrderedDict
from heapq import heapify, heappush, heappop
sys.setrecursionlimit(10 ** 6)
input = lambda : sys.stdin.readline()
I = lambda : int(input())
S = lambda : input().strip()
M = lambda : map(int, input().strip().split())
L = lambda : list(map(int, input().strip().split()))
mod = 10 ** 9 + 7

def dfs(node, par, x):
	v[node] = 1
	ans = x
	j = 1 if par == -1 else 2
	for i in adj[node]:
		if not v[i]:
			ans *= dfs(i, node, c - j)
			ans %= mod
			j += 1
	return ans
(n, c) = M()
adj = {i + 1: [] for i in range(n)}
for i in range(n - 1):
	(u, v) = M()
	adj[u].append(v)
	adj[v].append(u)
v = [0] * (n + 1)
fans = dfs(1, -1, c)
fans %= mod
print(fans)


import sys
from queue import Queue
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
mod = 10 ** 9 + 7
for _ in range(1):
	(n, c) = map(int, input().split())
	adj = [[] for _ in range(n + 1)]
	for _ in range(n - 1):
		(u, v) = map(int, input().split())
		adj[u].append(v)
		adj[v].append(u)
	q = Queue()
	vis = [False] * (n + 1)
	q.put((1, c))
	vis[1] = True
	ans = c
	while not q.empty():
		(node, C) = q.get()
		i = 1
		for child in adj[node]:
			if not vis[child]:
				ans *= C - i
				ans %= mod
				q.put((child, max(C - i, c - 1)))
				i += 1
				vis[child] = True
	print(ans)


import sys
import threading
input = sys.stdin.readline
sys.setrecursionlimit(3 * 10 ** 6)
global k
k = 10 ** 9 + 7

def dfs(vertex, gp, visited, c):
	global v
	global k
	global ans
	if vertex == 0:
		visited[vertex] = 1
		ans *= c
	for i in range(len(gp[vertex])):
		if visited[gp[vertex][i]] == 1:
			c += 1
		else:
			visited[gp[vertex][i]] = 1
			ans = ans * max(0, c - i - 1) % k
			dfs(gp[vertex][i], gp, visited, v - 1)
	return

def main():
	global ans
	global v
	(n, v) = map(int, input().split())
	gp = []
	for i in range(n):
		gp.append([])
	for i in range(n - 1):
		(x, y) = map(int, input().split())
		gp[x - 1].append(y - 1)
		gp[y - 1].append(x - 1)
	visited = [0] * n
	ans = 1
	dfs(0, gp, visited, v)
	print(ans)
threading.stack_size(10 ** 9)
t = threading.Thread(target=main)
t.start()
t.join()


import math
import sys
sys.setrecursionlimit(10 ** 6)
MOD = 10 ** 9 + 7
for _ in range(1):
	(N, C) = map(int, input().split())
	edges = {}
	for i in range(1, N + 1):
		edges[i] = []
	for i in range(N - 1):
		(x, y) = map(int, input().split())
		edges[x].append(y)
		edges[y].append(x)
	visited = set()
	ans = {1: C}
	dummy = {1: C}

	def explore(X):
		visited.add(X)
		rem = dummy[1]
		if X == 1:
			rem -= 1
		else:
			rem -= 2
		for ch in edges[X]:
			if ch not in visited:
				ans[ch] = rem
				visited.add(ch)
				explore(ch)
				rem -= 1
		return
	ans = {1: C}
	visited.add(1)
	explore(1)
	A = 1
	for i in ans:
		A *= ans[i]
		A %= MOD
	print(A)


import sys
sys.setrecursionlimit(10 ** 7)
(n, c) = map(int, input().split())
dit = {}
mod = 10 ** 9 + 7
for i in range(n - 1):
	(a, b) = map(int, input().split())
	if a in dit:
		dit[a].append(b)
	else:
		dit[a] = [b]
	if b in dit:
		dit[b].append(a)
	else:
		dit[b] = [a]
global ans
ans = 1

def fun(node, ad, p):
	global ans
	ans = ans * (c - ad) % mod
	if p == -1:
		adj = 1
	else:
		adj = 2
	if node not in dit:
		return
	for u in dit[node]:
		if u != p:
			fun(u, adj, node)
			adj += 1
fun(1, 0, -1)
print(ans)


I = lambda : list(map(int, input().split()))
(n, c) = I()
mod = 10 ** 9 + 7
deg = [0] * n
gr = [[] for i in range(n)]
for i in range(n - 1):
	(a, b) = I()
	deg[a - 1] += 1
	deg[b - 1] += 1
	gr[a - 1].append(b - 1)
	gr[b - 1].append(a - 1)
vis = [0] * n
fact = [1] * (10 ** 6 + 2)
for i in range(2, len(fact)):
	fact[i] = i * fact[i - 1] % mod

def ncr(n, r):
	den = pow(fact[n - r] * fact[r], mod - 2, mod)
	return fact[n] * den % mod
if max(deg) + 1 > c:
	an = 0
else:
	an = 1
	st = [[0, c]]
	while st:
		cur = st.pop()
		node = cur[0]
		vis[node] = 1
		an = an * cur[1] % mod
		if node == 0:
			val = c - 1
		else:
			val = c - 2
		for j in gr[node]:
			if not vis[j]:
				vis[j] = 1
				st.append([j, val])
				val -= 1
print(an)


(n, c) = map(int, input().split())
mp = {}
mp1 = {}
for i in range(n - 1):
	(x, y) = map(int, input().split())
	if x in mp:
		mp[x].append(y)
	else:
		mp[x] = [y]
root = list(mp.keys())[0]
mp2 = {}
mod = 1000000000.0 + 7
ans = 1
q = [root]
c2 = c
mp2[root] = c
while len(q):
	temp = []
	while len(q):
		k = q.pop()
		if mp2[k] < c:
			c2 = c - 1
		if k in mp:
			for i in mp[k]:
				temp.append(i)
				c2 -= 1
				mp2[i] = c2
	q = temp
for i in mp2:
	ans = mp2[i] * ans % mod
	ans %= mod
print(int(ans))


import sys
sys.setrecursionlimit(1000001)
scan = sys.stdin.readline
import math
(N, C) = map(int, input().strip().split())
tree = []
v = set([])
i = 0
while i <= N:
	tree.append([])
	i = i + 1
i = 0
while i < N - 1:
	temp = list(map(int, input().strip().split()))
	tree[temp[0]].append(temp[1])
	tree[temp[1]].append(temp[0])
	i = i + 1

def rec(x):
	r = 1
	v.add(x)
	l = len(tree[x])
	k = 0
	if x == 1:
		j = 1
	else:
		j = 2
	while k < l:
		if tree[x][k] not in v:
			r = r * ((C - j) * rec(tree[x][k])) % 1000000007 % 1000000007
			j = j + 1
		k = k + 1
	return r
print(C * rec(1) % 1000000007)


from sys import stdin
input = stdin.readline
(n, c) = map(int, input().split())
d = {}
mod = 10 ** 9 + 7
for i in range(n - 1):
	(u, v) = map(int, input().split())
	if u not in d:
		d[u] = 0
	d[u] += 1
	if v not in d:
		d[v] = 0
	d[v] += 1
ans = c
for i in range(d[1]):
	ans = ans * (c - i - 1) % mod
for i in range(2, n + 1):
	for j in range(d[i] - 1):
		ans = ans * (c - 2 - j) % mod
print(ans)


import collections
import math
from queue import Queue
[n, c] = [int(i) for i in input().split()]
parent = [-1] * n
mod = 10 ** 9 + 7
for i in range(n - 1):
	[u, v] = [int(j) for j in input().split()]
	a = min(u - 1, v - 1)
	b = max(u - 1, v - 1)
	parent[b] = a
ans = c
parent = parent[1:]
d = collections.Counter(parent)
for i in d:
	if i == 0:
		val = 1
	else:
		val = 2
	for j in range(d[i]):
		ans = ans * (c - val - j) % mod
print(ans)


from collections import deque
(n, c) = map(int, input().split())
adj = [[] for k in range(n)]
for i in range(n - 1):
	(u, v) = map(int, input().split())
	adj[u - 1].append(v - 1)
pro = 1
que = deque([[0, c, 0]])
while que:
	(node, val, level) = que.popleft()
	pro = pro * val % (10 ** 9 + 7)
	if val == 0:
		break
	if level < 1:
		v = val - 1
	else:
		v = c - 2
	for a in adj[node]:
		que.append([a, v, level + 1])
		v -= 1
print(pro)


[n, c] = list(map(int, input().split(' ')))
hm = {}
m = 10 ** 9 + 7
for i in range(n - 1):
	[u, v] = list(map(int, input().split(' ')))
	if u in hm:
		hm[u] += [v]
	else:
		hm[u] = [v]
ans = c
for i in range(len(hm[1])):
	ans = ans * (c - i - 1) % m
for (k, v1) in hm.items():
	if k != 1:
		d = len(v1)
		for j in range(d):
			ans = ans * (c - 2 - j) % m
print(ans)


mod = 10 ** 9 + 7
(n, c) = [int(item) for item in input().split(' ')]
neighbers = {}
for i in range(n - 1):
	(source, target) = [int(item) for item in input().split(' ')]
	if not neighbers.__contains__(source):
		neighbers[source] = []
	neighbers[source].append(target)
	if not neighbers.__contains__(target):
		neighbers[target] = []
	neighbers[target].append(source)
res = 1
first_node = 1
res *= c
for i in range(c - len(neighbers[first_node]), c):
	res = res * i % mod
for (parent, child_c) in neighbers.items():
	if parent != first_node and len(child_c) != 1:
		for i in range(c - len(child_c), c - 1):
			res = res * i % mod
print(res)


ri = lambda : int(input())
rl = lambda : list(map(int, input().split()))
rs = lambda : input()
from collections import defaultdict
import sys
sys.setrecursionlimit(100000)
M = 1000000007

def find(n, r):
	if r > n:
		flag = 0
		return 0
	total = 1
	for i in range(n - r + 1, n + 1):
		total = total * i
		total %= M
	return total
(n, c) = rl()
adj = {}
parent = set()
child = set()
for i in range(n - 1):
	(x, y) = map(int, input().split())
	if x not in adj:
		adj[x] = [y]
	else:
		adj[x].append(y)
	parent.add(x)
	child.add(y)
for x in parent:
	if x not in child:
		root = x
		break
ways = 0
for i in adj:
	if i == root:
		f = c * find(c - 1, len(adj[i]))
		f %= M
		ways = ways + f
		ways %= M
	else:
		f = find(c - 2, len(adj[i]))
		f %= M
		ways = ways * f
		ways %= M
print(ways)


from sys import stdin
from sys import setrecursionlimit
input = stdin.readline
setrecursionlimit(int(1000000000.0))

def ii():
	return int(input())

def li():
	return list(map(int, input().split()))
from math import sqrt

def perfect_sq(n):
	x = int(sqrt(n))
	while x * x < n:
		x += 1
	while x * x > n:
		x -= 1
	return x * x == n
mod = int(1000000000.0) + 7
(n, c) = li()
graph = [[] for i in range(n + 1)]
ans = [c for i in range(n + 1)]
for i in range(n - 1):
	(u, v) = li()
	graph[u].append(v)
	graph[v].append(u)

def dfs(at, p=0):
	cnt = 1 + (p > 0)
	for child in graph[at]:
		if child == p:
			continue
		ans[child] -= cnt
		cnt += 1
		dfs(child, at)
dfs(1)
val = 1
for i in range(1, n + 1):
	val = val * max(0, ans[i]) % mod
print(val)


import sys, math, heapq, bisect
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6 + 5)
ints = lambda : list(map(int, input().split()))

def gprint(t, ans=''):
	print(f'Case #{t + 1}:', ans)
p = 10 ** 9 + 7
inf = 10 ** 20 + 7

def dfs(node, c, isRoot):
	done.add(node)
	ans = 1
	if isRoot:
		start = c - 1
	else:
		start = c - 2
	for i in tree[node]:
		if i not in done:
			ans = ans * start * dfs(i, c, False) % p
			start -= 1
	return ans
(n, c) = ints()
tree = [[] for i in range(n + 1)]
for i in range(n - 1):
	(x, y) = ints()
	tree[x].append(y)
	tree[y].append(x)
done = set()
ans = c * dfs(1, c, True)
print(ans % p)