Read problem statements in [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

There is a large tree house in an unknown world. It is ruled by the great emperor KZS. It consists of $N$ nodes numbered from $1$ to $N$ in which the people of that world reside. The nodes are organized in a tree structure rooted at node $1$. You need to assign values to the nodes according to the wishes of emperor KZS which are as follows :-

The value of node $1$ is $X$.
All immediate children of any node have pairwise distinct values.                                   
For every node with at least one immediate child, the $\gcd$ of the values of all immediate children is equal to the value of the node.                                                                                                                                           
The total sum of the values of all nodes should be minimum.

The greatest common divisor $\gcd(a,b)$ of two positive integers $a$ and $b$ is equal to the largest integer $d$ such that both integers $a$ and $b$ are divisible by $d$.

Print the sum of all values, modulo $10^{9} + 7$.

------ Input ------

The first line contains an integer $T$, the number of test cases. $T$ testcases follow.  
The first line of each test contains two integers $N$ and $X$.
Each of the following $N-1$ lines contains two integers $u$ and $v$, denoting an edge between nodes $u$ and $v$.                               

------ Output ------

For each test case, print the sum of values, modulo $10^{9} + 7$.

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

$1 ≤ T ≤ 15$                                     
$2 ≤ N ≤ 3 \cdot 10^{5}$                                            
$1 ≤ X ≤ 10^{9}$                                    
$1 ≤ u, v ≤ N$ and $u \neq v$  
The given edges form a tree
The sum of $N$ over all test cases doesn't exceed $3 \cdot 10^{5}$.          

------ Subtasks ------
Subtask #1 (100 points): Original Constraints

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

4 1

1 2

1 3

1 4

8 1

1 2

1 3

2 4

2 5

5 6

5 7

7 8
----- Sample Output 1 ------ 
7

11
----- explanation 1 ------ 
In test case $1$, we will give values $1$, $2$, $3$ to the nodes $2$, $3$ and $4$ respectively.
So, the total sum will be $1 + 1 + 2 + 3 = 7$.

Difficulty: HARD
Tags: Graph algorithms

Graph traversal

Number theory

Mathematics

Data structures
Skill types: Data structures

Starter code:

Solutions:
import sys
sys.setrecursionlimit(110000)
mod = 10 ** 9 + 7

def solve(t, i, parent):
	arr = []
	for child in t[i]:
		if child != parent:
			arr.append(solve(t, child, i))
	arr.sort(reverse=True)
	_sum = 1
	for (i, j) in enumerate(arr):
		_sum += (i + 1) * j
	return _sum
for _ in range(int(input())):
	(n, x) = list(map(int, input().split(' ')))
	t = [[] for i in range(n + 1)]
	for i in range(n - 1):
		(u, v) = list(map(int, input().split(' ')))
		t[u].append(v)
		t[v].append(u)
	print(x * solve(t, 1, 0) % mod)


from sys import setrecursionlimit
setrecursionlimit(1000000)
M = 1000000007

def dfs(adj, node, parent):
	ans = 1
	values = []
	children = adj.get(node, [])
	for child in children:
		if child != parent:
			values.append(dfs(adj, child, node))
	values.sort(reverse=True)
	for i in range(len(values)):
		ans += values[i] * (i + 1)
	return ans
T = int(input())
for _ in range(T):
	(n, x) = map(int, input().split())
	adj = {}
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		try:
			adj[u].append(v)
		except:
			adj[u] = [v]
		try:
			adj[v].append(u)
		except:
			adj[v] = [u]
	print(dfs(adj, 1, 0) % M * x % M)


import sys
sys.setrecursionlimit(10 ** 7)

def dfs(root):
	arr = []
	visited.add(root)
	for node in graph[root]:
		if node not in visited:
			arr.append(dfs(node))
	arr.sort(reverse=True)
	summ = 1
	for (k, v) in enumerate(arr):
		summ += (k + 1) * v
	return summ
from collections import defaultdict
t = int(input())
for _ in range(t):
	(n, x) = map(int, input().split())
	graph = defaultdict(list)
	visited = set()
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		graph[u].append(v)
		graph[v].append(u)
	print(x * dfs(1) % (10 ** 9 + 7))


import sys
sys.setrecursionlimit(10 ** 6)
p = 10 ** 9 + 7

def findSum(node, children, parent):
	if parent != -1 and len(children[node]) == 1:
		return 1
	childSums = []
	for child in children[node]:
		if child == parent:
			continue
		s = findSum(child, children, node)
		childSums.append((child, s))
	childSums.sort(key=lambda x: x[1], reverse=True)
	totalSum = 1
	for i in range(len(childSums)):
		totalSum += childSums[i][1] * (i + 1)
	return totalSum
t = int(input())
for i in range(t):
	(n, x) = map(int, input().split())
	children = {x: [] for x in range(n)}
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		children[u - 1].append(v - 1)
		children[v - 1].append(u - 1)
	print(findSum(0, children, -1) * x % p)


import sys
sys.setrecursionlimit(300034)
p = 10 ** 9 + 7

def tsum(nd, ar):
	if len(ar[nd]) == 0:
		return 1
	s = 0
	li = []
	for i in ar[nd]:
		li.append(tsum(i, ar))
	li = sorted(li)
	l = len(li)
	for i in li:
		s += i * l
		l -= 1
	s += 1
	return s

def assg(p, no, ar, far):
	if ar[no] == [p] or ar[no] == []:
		return far
	for i in ar[no]:
		if i != p:
			far[no].append(i)
			assg(no, i, ar, far)
	return far
t = int(input())
for _ in range(t):
	(n, x) = map(int, input().split())
	ar = [[] for i in range(n + 7)]
	far = [[] for i in range(n + 7)]
	ls = [0] * (n + 1)
	ls[1] = 1
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		ar[u].append(v)
		ar[v].append(u)
	far = assg(0, 1, ar, far)
	print(x * (tsum(1, far) % p) % p)


from sys import setrecursionlimit
setrecursionlimit(1 << 30)

def dfs(child, parent, graph):
	count = 1
	child_arr = []
	for ele in graph[child]:
		if ele != parent:
			child_arr.append(dfs(ele, child, graph))
	child_arr.sort(reverse=True)
	for (i, j) in enumerate(child_arr):
		count += (i + 1) * j
	return count
M = 1000000007
for _ in range(int(input())):
	(n, x) = map(int, input().split())
	graph = {}
	for i in range(1, n + 1):
		graph[i] = []
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		graph[u].append(v)
		graph[v].append(u)
	print(x * (dfs(1, -1, graph) % M) % M)


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

def value(v, x, parent):
	l = []
	for node in adj[v]:
		if node != parent:
			l.append(value(node, x, v))
	l.sort(reverse=True)
	ans = x
	for (i, val) in enumerate(l):
		ans += (i + 1) * val
	return ans
for _ in range(int(input())):
	(n, x) = map(int, input().split())
	adj = defaultdict(list)
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		adj[u].append(v)
		adj[v].append(u)
	print(x * value(1, 1, -1) % mod)


import sys
from os import path
import math
import time
from collections import defaultdict
from sys import setrecursionlimit
setrecursionlimit(10 ** 8)
MOD = 10 ** 9 + 7
INT_MAX = 10 ** 9
if path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

def dfs(v, p):
	b = []
	ans = 1
	for i in tree[v]:
		if i != p:
			b.append(dfs(i, v))
	b = sorted(b, reverse=True)
	x = 1
	for i in range(len(b)):
		ans += b[i] * x
		x += 1
	return ans
t = int(input())
for _ in range(t):
	(N, X) = map(int, input().split())
	tree = defaultdict(list)
	parent = []
	ans = 1
	for i in range(N - 1):
		(u, v) = map(int, input().split())
		tree[u].append(v)
		tree[v].append(u)
	ans = dfs(1, -1)
	print(X * ans % MOD)


import sys
sys.setrecursionlimit(3 * int(100000.0) + 11)
MOD = int(1000000000.0) + 7

def dfs(node, parent):
	subtree_values = []
	for child in graph[node]:
		if child != parent:
			child_val = dfs(child, node)
			subtree_values.append(child_val)
	subtree_values.sort(reverse=True)
	children = len(graph[node]) - (1 if node != 1 else 0)
	node_val = children * (children + 1) // 2
	for i in range(len(subtree_values)):
		node_val += (i + 1) * subtree_values[i]
	return node_val

def solve():
	root_val = dfs(1, 1) + 1
	return X * root_val % MOD
test_cases = int(input())
for test_case in range(test_cases):
	(N, X) = map(int, input().split())
	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)
	print(solve())


def solve():
	child = {}
	parent = {}
	(depth, max_depth) = ({}, 1)
	for (u, v) in edges:
		child.setdefault(u, []).append(v)
		child.setdefault(v, []).append(u)
	used = set()
	(que, p_que) = ([1], 0)
	depth[1] = 1
	used.add(1)
	while p_que < len(que):
		node = que[p_que]
		child[node] = [x for x in child[node] if x not in used]
		for x in child[node]:
			used.add(x)
		child_depth = depth[node] + 1
		for x in child[node]:
			que.append(x)
			parent[x] = node
			depth[x] = child_depth
			if child_depth > max_depth:
				max_depth = child_depth
		p_que += 1
	level = [set() for x in range(max_depth)]
	level[0].add(1)
	for node in child:
		for x in child[node]:
			level[depth[node]].add(x)
	weight = {x: 0 for x in range(N + 1)}
	for l in range(max_depth - 1, 0, -1):
		used = set()
		for node in level[l]:
			if node in used:
				continue
			p = parent[node]
			lc = len(child[p])
			for (i, ci) in enumerate(sorted(child[p], key=lambda x: weight[x], reverse=True), start=1):
				weight[p] += i * (weight[ci] + 1)
				used.add(ci)
	return (weight[1] + 1) * X % MOD
MOD = 10 ** 9 + 7
for _ in range(int(input())):
	(N, X) = [int(x) for x in input().split()]
	edges = [[int(x) for x in input().split()] for i in range(N - 1)]
	print(solve())


import sys
sys.setrecursionlimit(10 ** 9)
mod = 1000000007

def dfs(rt, par):
	for g in graph[rt]:
		if g != par:
			dfs(g, rt)
	c = []
	for g in graph[rt]:
		if g != par:
			c.append(g)
	c.sort(reverse=True, key=lambda x: sm[x])
	_m = 1
	for i in c:
		m[i] = _m
		_m += 1
	for g in graph[rt]:
		if g != par:
			sm[rt] += m[g] * sm[g]
for _ in range(int(input())):
	(n, x) = map(int, input().split())
	graph = [[] for _ in range(n + 1)]
	for i in range(n - 1):
		(s, e) = map(int, input().split())
		graph[s].append(e)
		graph[e].append(s)
	sm = [1 for i in range(n + 1)]
	m = [0 for i in range(n + 1)]
	dfs(1, 0)
	print(sm[1] % mod * x % mod)


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

def solve(ver):
	vist[ver - 1] = 1
	l = []
	for i in range(len(d[ver])):
		if vist[d[ver][i] - 1] == 0:
			tmp = solve(d[ver][i])
			l.append(tmp)
	l.sort(reverse=True)
	ans = 1
	for i in range(len(l)):
		ans += (i + 1) * l[i]
		ans = ans
	return ans
t = int(input())
while t != 0:
	mod = int(1000000000.0 + 7)
	(n, x) = map(int, input().split())
	d = defaultdict(list)
	for i in range(n - 1):
		(a, b) = map(int, input().split())
		d[a].append(b)
		d[b].append(a)
	vist = [0 for i in range(n)]
	x = x % mod
	print(solve(1) % mod * x % mod)
	t -= 1


from sys import setrecursionlimit
from collections import defaultdict
setrecursionlimit(1 << 30)
MOD = pow(10, 9) + 7

def dfs(n, p, graph):
	count = 1
	child = []
	for i in graph[n]:
		if i == p:
			continue
		child.append(dfs(i, n, graph))
	child.sort(reverse=True)
	for (i, j) in enumerate(child):
		count += (i + 1) * j
	return count

def solve():
	(n, x) = map(int, input().split())
	graph = defaultdict(list)
	for _ in range(n - 1):
		(a, b) = map(int, input().split())
		graph[a].append(b)
		graph[b].append(a)
	result = dfs(1, -1, graph) % MOD
	result = result * x % MOD
	return result
t = 1
t = int(input())
for _ in range(t):
	print(solve())


from sys import setrecursionlimit
setrecursionlimit(10 ** 6)
MODULO = 10 ** 9 + 7
test_cases = int(input().strip())

class Tree:

	def __init__(self):
		self.children = dict()

	def add_edge(self, node1, node2):
		if node1 in self.children:
			self.children[node1].append(node2)
		else:
			self.children[node1] = [node2]
		if node2 in self.children:
			self.children[node2].append(node1)
		else:
			self.children[node2] = [node1]

def compute_value(t, node, parent_node):
	if node in t.children:
		child_values = [compute_value(t, y, node) for y in t.children[node] if y != parent_node]
		child_values.sort(reverse=True)
		child_sum = 0
		for (idx, el) in enumerate(child_values):
			child_sum = child_sum + el * (idx + 1)
		return 1 + child_sum
	else:
		return 1
while test_cases > 0:
	test_cases -= 1
	[n, x] = list(map(int, input().strip().split()))
	tree = Tree()
	for i in range(n - 1):
		[u, v] = list(map(int, input().strip().split()))
		tree.add_edge(u, v)
	val = compute_value(tree, 1, 0)
	val = val * x % MODULO
	print(val)


from sys import stdin, stdout, setrecursionlimit
from math import ceil, floor, sqrt, log, log2, log10
from collections import Counter
setrecursionlimit(pow(10, 6))
input = stdin.readline

def solve():
	pass
t = int(input())
maxx = 3 * 10 ** 5 + 2

def dfs(v, p):
	b = []
	for i in range(len(edges[v])):
		if edges[v][i] == p:
			continue
		else:
			b.append(dfs(edges[v][i], v))
	b.sort(reverse=True)
	out = 1
	k = 1
	for i in b:
		out += i * k
		k += 1
	return out
for _ in range(t):
	(n, x) = map(int, input().split())
	edges = [[] for i in range(n + 1)]
	for i in range(n - 1):
		(a, b) = map(int, input().split())
		edges[a].append(b)
		edges[b].append(a)
	output = dfs(1, -1) % 1000000007
	print(output * x % 1000000007)


import heapq as h
import sys
sys.setrecursionlimit(300000)

def subCount(root=1, parent=None):
	children = d.get(root, [])
	if parent is not None and len(children) == 1:
		return 1
	count = 1
	pq = []
	for i in children:
		if i != parent:
			h.heappush(pq, subCount(i, root))
	for i in range(len(pq), 0, -1):
		count += i * h.heappop(pq)
	return count
t = int(input())
for i in range(t):
	(n, x) = map(int, input().split())
	d = {}
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		if d.get(u, 0) == 0:
			d[u] = [v]
		else:
			d[u].append(v)
		if d.get(v, 0) == 0:
			d[v] = [u]
		else:
			d[v].append(u)
	vals = subCount() * x
	print(vals % 1000000007)


from collections import defaultdict
from functools import cmp_to_key
import sys
sys.setrecursionlimit(200000)
d = defaultdict(list)
M = 10 ** 9 + 7

def dfs1(src, parent, d):
	s = []
	for g in d[src]:
		if g == parent:
			continue
		ans = dfs1(g, src, d)
		s.append(ans)
	s.sort(reverse=True)
	val = 1
	res = 1
	for t in s:
		res += t * val
		val += 1
	return res
for _ in range(int(input())):
	(N, X) = map(int, input().split())
	d.clear()
	for _ in range(N - 1):
		(src, dest) = map(int, input().split())
		d[src].append(dest)
		d[dest].append(src)
	ans = dfs1(1, -1, d)
	print(ans * X % M)


from collections import deque
import sys
sys.setrecursionlimit(10 ** 6)
MOD = 1000000007

class Solution:

	def solve(self, tree, n, x):
		values = [0] * n

		def dfs(s, e):
			values[s] = 1
			tmp = []
			for u in tree[s]:
				if u == e:
					continue
				dfs(u, s)
				tmp.append(values[u])
			tmp.sort(reverse=True)
			for i in range(len(tmp)):
				values[s] += (i + 1) * tmp[i]
		dfs(0, -1)
		return values[0] * x % MOD
sol = Solution()
for _ in range(int(input())):
	(n, x) = [int(y) for y in input().split()]
	tree = [[] for i in range(n)]
	for i in range(n - 1):
		(u, v) = [int(y) for y in input().split()]
		tree[u - 1].append(v - 1)
		tree[v - 1].append(u - 1)
	print(sol.solve(tree, n, x))


import sys
from collections import defaultdict
sys.setrecursionlimit(10 ** 8)
mx = 3 * 100000 + 2
mod = 1000000007

def tt(p):
	vis[p] = 1
	for c in l[p]:
		if not vis[c]:
			tt(c)
	l[p].sort(key=lambda x: ans[x], reverse=True)
	ans[p] = 1
	for i in range(1, len(l[p]) + 1):
		ans[p] += i * ans[l[p][i - 1]]
t = int(input())
for _ in range(t):
	(n, x) = map(int, input().split())
	l = defaultdict(list)
	vis = [0] * mx
	ans = [0] * mx
	for i in range(n - 1):
		(a, b) = map(int, input().split())
		l[a].append(b)
		l[b].append(a)
	tt(1)
	print(ans[1] % mod * x % mod % mod)


import sys
sys.setrecursionlimit(pow(10, 6))
vis = set()

def dfs(c):
	ans = 1
	nans = []
	vis.add(c)
	for i in g[c]:
		if i in vis:
			continue
		nans.append(dfs(i))
	k = sorted(nans, reverse=True)
	for (i, j) in enumerate(k):
		ans += j * (i + 1)
	return ans
m = 1000000007
for _ in range(int(input())):
	vis = set()
	(n, x) = map(int, input().split(' '))
	g = list(([] for i in range(n + 1)))
	for i in range(n - 1):
		(u, v) = map(int, input().split(' '))
		g[u].append(v)
		g[v].append(u)
	print(dfs(1) * x % m)


from collections import defaultdict as dd
import sys
sys.setrecursionlimit(1000000000)
for tc in range(int(input())):
	(n, k) = map(int, input().split())
	tree = dd(set)
	for i in range(n - 1):
		(x, y) = map(int, input().split())
		tree[x].add(y)
		tree[y].add(x)

	def assignValues(root, par):
		children = []
		for child in tree[root]:
			if child == par:
				continue
			sumOfValues = assignValues(child, root)
			children.append((child, sumOfValues))
		children = sorted(children, key=lambda x: x[1], reverse=True)
		ans = 1
		assignVal = 1
		for (child, sumOfValues) in children:
			ans += assignVal * sumOfValues
			assignVal += 1
		return ans
	ans = assignValues(1, 0)
	print(k * (ans % 1000000007) % 1000000007)


mod = 1000000007
from collections import defaultdict
import sys
sys.setrecursionlimit(10 ** 8)

def dfs(current, parent, g, dp, total):
	dp[current] = 1
	total[current] = dp[current]
	s = 0
	for i in range(len(g[current])):
		node = g[current][i]
		if node != parent:
			dp[current] += 2 * dp[node] % mod
			dp[current] %= mod
			total[current] += total[node]
			total[current] %= mod
			total[current] += dp[node]
			total[current] %= mod
			s += dp[node]

def solve(r, p, mul, smul):
	for nd in graph[r]:
		if nd != p:
			solve(nd, r, mul, smul)
	c = []
	for nd in graph[r]:
		if nd != p:
			c.append(nd)
	c.sort(reverse=True, key=lambda x: smul[x])
	_mul = 1
	a = 0
	for i in range(10):
		a += i
	for j in range(1, 10, 10):
		a += j
	for i in c:
		mul[i] = _mul
		_mul += 1
	for value in graph[r]:
		if value != p:
			smul[r] += mul[value] * smul[value]

def solve1(a, b, k):
	f = 0
	ans = 0
	for i in range(k):
		if a[i] == b[i]:
			f = 1
		elif f:
			ans = ans + 2
			f = 0
	if a[1] != b[1]:
		ans = ans - 1
	return ans
for _ in range(int(input())):
	(n, x) = map(int, input().split())
	graph = defaultdict(list)
	for i in range(n - 1):
		(a, b) = map(int, input().split())
		graph[a].append(b)
		graph[b].append(a)
	smul = [1 for i in range(n + 1)]
	mul = [0 for i in range(n + 1)]
	solve(1, 0, mul, smul)
	print(smul[1] % mod * x % mod)


try:
	import sys
	mod = 1000000007
	sys.setrecursionlimit(1000000)

	def solve(node, previous):
		for adj in subnodes[node]:
			if adj != previous:
				solve(adj, node)
		b = []
		for i in subnodes[node]:
			if i != previous:
				b.append([count[i], i])
		b.sort(reverse=True)
		init = 1
		for i in b:
			res[i[1]] = init
			init += 1
		for i in subnodes[node]:
			if i != previous:
				count[node] += res[i] * count[i]
	t = int(input())
	for i in range(t):
		(n, x) = map(int, input().strip().split())
		subnodes = [[] for i in range(n + 1)]
		for i in range(n - 1):
			(u, v) = map(int, input().strip().split())
			subnodes[u].append(v)
			subnodes[v].append(u)
		count = [1] * (n + 1)
		res = [0] * (n + 1)
		solve(1, -1)
		ans = count[1] % mod * x % mod
		print(ans % mod)
except:
	pass


mod = 10 ** 9 + 7

def sdfdsfsdf(v):
	temp = []
	temp.append(v)
	while temp:
		k = temp[-1]
		if visited[k] == 1:
			temp.pop()
			continue
		visited[k] = -1
		flag = 0
		if inx[k] < len(asdsad[k]):
			asdsadsddsfsdf = asdsad[k][inx[k]]
			inx[k] += 1
			if visited[asdsadsddsfsdf] == 0:
				temp.append(asdsadsddsfsdf)
				visited[asdsadsddsfsdf] = -1
		else:
			child = []
			factor = 0
			for i in asdsad[k]:
				child.append((val[i], i))
				factor += 1
			child.sort()
			t_x_par = 0
			for j in child:
				tt = j[0] * factor
				t_x_par += tt
				factor -= 1
			t_x_par += 1
			val[k] = t_x_par
			visited[temp.pop()] = 1
for _ in range(int(input())):
	(n, x) = map(int, input().split())
	asdsad = [[0, 0] for i in range(n)]
	visited = [0 for i in range(n)]
	val = [0 for i in range(n)]
	inx = [2 for i in range(n)]
	for i in range(n - 1):
		(l, r) = map(int, input().split())
		l -= 1
		r -= 1
		asdsad[r].append(l)
		asdsad[l].append(r)
	sdfdsfsdf(0)
	print(val[0] % mod * x % mod)


n_max = int(300000.0 + 5)
mod = 10 ** 9 + 7
adjacent = []
lokesh = []
value = []
king = []
import sys
sys.setrecursionlimit(10 ** 6)

def dfs(cur, last=-1):
	for x in adjacent[cur]:
		if x == last:
			continue
		dfs(x, cur)
	king = []
	for x in adjacent[cur]:
		if x != last:
			king.append((lokesh[x], x))
	king.sort(reverse=True)
	nv = 1
	for (valuei, idv) in king:
		value[idv] = nv
		nv += 1
	for x in adjacent[cur]:
		if x != last:
			lokesh[cur] += value[x] * lokesh[x]
for _ in range(int(input())):
	(n, x) = [int(i) for i in input().split()]
	lokesh = [1 for i in range(n)]
	value = [0 for i in range(n)]
	adjacent = [[] for i in range(n_max)]
	for j in range(n - 1):
		(u, v) = [int(i) - 1 for i in input().split()]
		adjacent[u].append(v)
		adjacent[v].append(u)
	dfs(0)
	print(lokesh[0] % mod * x % mod)


from queue import Queue
test = int(input())
for i in range(test):
	(N, X) = map(int, input().strip().split())
	ar = []
	lis = []
	ab = [0] * (N + 1)
	ab[1] = 1
	ze = 0
	l = []
	v = []
	ze = 0
	ze = 0
	for l in range(N + 1):
		lis.append([])
		v.append([])
	for j in range(N - 1):
		(a, b) = map(int, input().strip().split())
		v[a].append(b)
		v[b].append(a)
	for x in v[1]:
		ar.append([1, x])
		ab[x] = 1
		q = Queue(maxsize=0)
		q.put(x)
		while q.empty() == False:
			o = q.get()
			for y in v[o]:
				if ab[y] == 0:
					ar.append([o, y])
					ab[y] = 1
					q.put(y)
	for j in range(N - 2, -1, -1):
		r = 1
		f = 0
		lis[ar[j][1]].sort(reverse=True)
		for l in lis[ar[j][1]]:
			f += r * l
			r = r + 1
		lis[ar[j][0]].append(f + 1)
	r = 1
	f = 0
	lis[1].sort(reverse=True)
	for l in lis[1]:
		f += r * l
		r = r + 1
	print((f * X + X) % (10 ** 9 + 7))


from collections import deque
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)

def conv_2_directed(node):
	visited[node] = 1
	a = list(span_tr[node])
	for x in a:
		if visited[x] == 1:
			span_tr[node].remove(x)
		else:
			conv_2_directed(x)

def treehouse(z):
	children = span_tr[z]
	if span_tr[z]:
		arr = []
		k = 0
		for node in children:
			arr.append(treehouse(node))
		arr.sort(reverse=True)
		i = 1
		for val in arr:
			k += val * i + i
			i += 1
		return k
	return 0
t = int(input())
while t:
	(n, x) = map(int, input().split())
	span_tr = {}
	for __ in range(n - 1):
		(a, b) = map(int, input().split())
		if a not in span_tr:
			span_tr[a] = [b]
		else:
			span_tr[a].append(b)
		if b not in span_tr:
			span_tr[b] = [a]
		else:
			span_tr[b].append(a)
	visited = [0] * (n + 1)
	conv_2_directed(1)
	ans1 = treehouse(1) + 1
	ansx = ans1 * x
	print(ansx % 1000000007)
	t -= 1


import sys
sys.setrecursionlimit(10000000)
from collections import deque

def find_sum(node):
	c = []
	if not tree[node]:
		return 1
	for x in tree[node]:
		if x != -1:
			c.append(find_sum(x))
	c.sort(reverse=True)
	s = 0
	for x in range(len(c)):
		s += (x + 1) * c[x]
	return s + 1

def directed():
	trash = set()
	edges = {}
	q = deque([1])
	while q:
		a = q.popleft()
		trash.add(a)
		edges[a] = []
		for u in tree[a]:
			if u not in trash:
				q.append(u)
				edges[a].append(u)
	return edges
k = 1000000007
t = int(input())
for _ in range(t):
	(n, x) = [int(i) for i in input().split()]
	tree = {}
	for __ in range(n - 1):
		(a, b) = map(int, input().split())
		if a in tree:
			tree[a].append(b)
		else:
			tree[a] = [b]
		(a, b) = (b, a)
		if a in tree:
			tree[a].append(b)
		else:
			tree[a] = [b]
	visited = [0] * n
	tree = directed()
	visited = [0] * n
	print(x * find_sum(1) % k)


import sys
sys.setrecursionlimit(10 ** 6)
from functools import cmp_to_key

def fcr(i, fc):
	return fc[i]

def compare(i1, i2):
	return fcr(i2, fc) - fcr(i1, fc)

def v(tree, root, fc, l):
	for i in tree[root]:
		if i == l:
			continue
		if len(tree[i]) > 0:
			v(tree, i, fc, root)
	tree[root].sort(key=cmp_to_key(compare))
	k = 1
	for i in tree[root]:
		if i != l:
			fc[root] += fc[i] * k
			k += 1
t = int(input())
for i in range(t):
	(n, x) = map(int, input().split())
	tree = [[] for x in range(n + 1)]
	for j in range(n - 1):
		(p, c) = map(int, input().split())
		tree[p].append(c)
		tree[c].append(p)
	fc = [1] * (n + 1)
	v(tree, 1, fc, -1)
	print(fc[1] * x % 1000000007)


import sys
sys.setrecursionlimit(10 ** 6)
m = 1000000007
for a0 in range(int(input())):
	(n, x) = [int(x) for x in input().split()]
	l = [[-1, -1] for i in range(n)]
	for i in range(n - 1):
		(a, b) = [int(x) for x in input().split()]
		l[a - 1].append(b - 1)
		l[b - 1].append(a - 1)

	def val(l, a, b):
		if l[a][0] != -1:
			return l[a][0]
		elif len(l[a]) < 3:
			l[a][0] = 1
		else:
			vp = []
			for i in range(2, len(l[a])):
				if l[a][i] != b:
					vp.append(val(l, l[a][i], a))
			vp.sort(reverse=True)
			l[a][0] = 1
			for i in range(len(vp)):
				l[a][0] += (i + 1) * vp[i]
		return l[a][0]
	print(val(l, 0, -1) * x % m)


from collections import defaultdict
import sys
sys.setrecursionlimit(300000)

def solution(k: str, l: str):
	for c in graph[k]:
		if c == l:
			continue
		solution(c, k)
	arr = sorted(((value[c], c) for c in graph[k] if c != l))
	for (key, val) in zip(arr, range(len(arr), 0, -1)):
		value[k] += val * key[0]
for _ in range(int(input())):
	graph = defaultdict(list)
	value = defaultdict(lambda : 1)
	(n, x) = map(int, input().split())
	for i in range(n - 1):
		(p, c) = input().split()
		graph[p].append(c)
		graph[c].append(p)
	solution('1', '0')
	print(value['1'] * x % 1000000007)


from queue import PriorityQueue
from queue import Queue
import math
from collections import defaultdict
import sys
import operator as op
from functools import reduce
sys.setrecursionlimit(10 ** 6)
ii = lambda : list(map(int, sys.stdin.readline().strip().split()))
ist = lambda : list(sys.stdin.readline().strip().split())
mod = 1000000007

def dfs(st, tree, subval, value, last=-1):
	for x in tree[st]:
		if x != last:
			dfs(x, tree, subval, value, st)
	cnt = []
	for x in tree[st]:
		if x != last:
			cnt.append((subval[x], x))
	cnt.sort(reverse=True)
	tmp = 1
	for (a, b) in cnt:
		value[b] = tmp
		tmp += 1
	for x in tree[st]:
		if x != last:
			subval[st] += value[x] * subval[x]
for _ in range(int(input())):
	(n, x) = ii()
	tree = [[] for k in range(n)]
	subval = [1 for k in range(n)]
	value = [0 for k in range(n)]
	for __ in range(n - 1):
		(u, v) = ii()
		tree[u - 1].append(v - 1)
		tree[v - 1].append(u - 1)
	dfs(0, tree, subval, value)
	print(subval[0] % mod * x % mod % mod)


import sys
M = 10 ** 9 + 7
sys.setrecursionlimit(100000000)

class Tree:

	def __init__(self, n):
		self.adj = [set() for _ in range(n + 1)]
		self.priority = [1 for _ in range(n + 1)]
		self.sum = 0

	def __dfs_assign(self, node, parent):
		if parent in self.adj[node]:
			self.adj[node].remove(parent)
		for v in self.adj[node]:
			self.__dfs_assign(v, node)
		for (i, v) in enumerate(sorted(self.adj[node], key=lambda n: self.priority[n], reverse=True), 1):
			self.priority[node] += self.priority[v] * i

	def __dfs_calc(self, node, parent, x):
		for (i, v) in enumerate(sorted(self.adj[node], key=lambda n: self.priority[n], reverse=True), 1):
			if v != parent:
				self.sum += x * i % M
				self.sum %= M
				self.__dfs_calc(v, node, x * i)

	def insertEdge(self, u, v):
		self.adj[u].add(v)
		self.adj[v].add(u)

	def assignValue(self):
		self.__dfs_assign(1, 0)

	def minSum(self, x):
		self.sum += x
		self.__dfs_calc(1, 0, x)
		return self.sum
for _ in range(int(input())):
	(n, x) = map(int, input().split())
	tree = Tree(n)
	for i in range(1, n):
		tree.insertEdge(*map(int, input().split()))
	tree.assignValue()
	print(tree.minSum(x))


import sys
from collections import defaultdict
sys.setrecursionlimit(3100000)
M = 1000000007
visited = [0] * (1000000 + 1)

def KZS(tree, node, level):
	visited[node] = 1
	for i in tree[node]:
		if visited[i]:
			continue
		level[node].append(KZS(tree, i, level))
	ll = len(level[node])
	level[node].sort(reverse=True)
	value = 1
	for i in range(ll):
		value += level[node][i] * (i + 1)
	return value
for _ in range(int(input())):
	(n, x) = map(int, input().split())
	tree = defaultdict(list)
	for i in range(0, n + 1):
		visited[i] = 0
	for i in range(n - 1):
		(a, b) = map(int, input().split())
		tree[a].append(b)
		tree[b].append(a)
	level = defaultdict(list)
	ans = KZS(tree, 1, level) % M
	print(ans * x % M)


import sys
sys.setrecursionlimit(5 * 10 ** 5)
modd = 1000000007
import collections

def depth(u, k=-1):
	for x in g[u]:
		if x == k:
			continue
		depth(x, u)
	chroot = []
	for x in g[u]:
		if x != k:
			chroot.append([ub[x], x])
	chroot.sort(reverse=True)
	text = 1
	for (vox, iddd) in chroot:
		alue[iddd] = text
		text = text + 1
	for x in g[u]:
		if x != k:
			ub[u] += alue[x] * ub[x]
for _ in range(int(input())):
	(n, yy) = map(int, input().split())
	g = collections.defaultdict(list)
	for i in range(n - 1):
		(x, y) = map(int, input().split())
		g[x - 1].append(y - 1)
		g[y - 1].append(x - 1)
	ub = [1] * n
	alue = [0] * n
	depth(0)
	sys.stdout.write(str(ub[0] % 1000000007 * yy % 1000000007 % 1000000007))
	print()


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

	def DepthFirstSearch(current, house, par, child, n, end):
		for i in house[current]:
			if i == end:
				continue
			DepthFirstSearch(i, house, par, child, n, current)
		children = []
		for i in house[current]:
			if i != end:
				children.append([par[i], i])
		children.sort(reverse=True)
		count = 1
		for i in children:
			child[i[1]] = count
			count += 1
		for i in house[current]:
			if i != end:
				par[current] += par[i] * child[i]
	for _ in range(int(input())):
		m = 10 ** 9 + 7
		(n, x) = map(int, input().split())
		par = [1] * n
		child = [0] * n
		house = defaultdict(list)
		for i in range(n - 1):
			(u, v) = map(int, input().split())
			house[u - 1].append(v - 1)
			house[v - 1].append(u - 1)
		DepthFirstSearch(0, house, par, child, n, -1)
		print(par[0] % m * (x % m) % m)
except:
	pass


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

def dfs(curr, tree, parent, child, n, end):
	for i in tree[curr]:
		if i == end:
			continue
		dfs(i, tree, parent, child, n, curr)
	children = []
	for i in tree[curr]:
		if i != end:
			children.append([parent[i], i])
	children.sort(reverse=True)
	cnt = 1
	for i in children:
		child[i[1]] = cnt
		cnt += 1
	for i in tree[curr]:
		if i != end:
			parent[curr] += parent[i] * child[i]
try:
	for test in range(int(input())):
		mod = 10 ** 9 + 7
		(N, X) = map(int, input().split())
		parent = [1] * N
		child = [0] * N
		tree = defaultdict(list)
		for i in range(N - 1):
			(u, v) = map(int, input().split())
			tree[u - 1].append(v - 1)
			tree[v - 1].append(u - 1)
		dfs(0, tree, parent, child, N, -1)
		print(parent[0] % mod * (X % mod) % mod)
except EOFError:
	pass


import sys
sys.setrecursionlimit(10 ** 8)
mytree = []
ansarr = []
myarr = []
ch = []
MOD = 1000000007

def DepthFirstSearch(present, lst):
	for x in mytree[present]:
		if x == lst:
			continue
		else:
			DepthFirstSearch(x, present)
	ch.clear()
	for x in mytree[present]:
		if x != lst:
			mylist = [ansarr[x], x]
			ch.append(mylist)
	ch.sort(reverse=True)
	tol = 1
	for t in ch:
		temp = t[1]
		myarr[temp] += tol
		tol += 1
	for x in mytree[present]:
		if x != lst:
			ansarr[present] += myarr[x] * ansarr[x]
for _ in range(int(sys.stdin.readline())):
	(n, m) = map(int, sys.stdin.readline().strip().split())
	myarr = [0] * n
	ansarr = [1] * n
	mytree = [[] for i in range(n)]
	for i in range(n - 1):
		(x, y) = map(int, sys.stdin.readline().strip().split())
		x -= 1
		y -= 1
		mytree[x].append(y)
		mytree[y].append(x)
	DepthFirstSearch(0, -1)
	Answer = ansarr[0] % MOD * m % MOD
	sys.stdout.write(str(Answer) + '\n')
	mytree.clear()
	myarr.clear()
	ansarr.clear()


import sys
sys.setrecursionlimit(10 ** 6)

def dfs(tree, node, parent):
	if len(tree[node]) == 0:
		return 0
	val = []
	for i in range(len(tree[node])):
		ans = 0
		if tree[node][i] != parent:
			ans = dfs(tree, tree[node][i], node)
			val.append(ans)
	val.sort(reverse=True)
	ans = 0
	count = 1
	for i in val:
		ans = ans + count + count * i
		count += 1
	return ans
t = int(input())
for i in range(t):
	(n, x) = list(map(int, input().strip().split()))
	tree = [[] for i in range(300005)]
	for j in range(n - 1):
		(u, v) = list(map(int, input().strip().split()))
		tree[u].append(v)
		tree[v].append(u)
	ans = (x + x * dfs(tree, 1, 0)) % (10 ** 9 + 7)
	print(ans)


import sys
sys.setrecursionlimit(300000)
mod = 10 ** 9 + 7

def dfs(now, adj, subval, val, lst=-1):
	for x in adj[now]:
		if x == lst:
			continue
		dfs(x, adj, subval, val, now)
	ch = []
	for x in adj[now]:
		if x != lst:
			ch.append([subval[x], x])
	ch.sort(key=lambda x: x[0], reverse=True)
	tok = 1
	for (_val, id) in ch:
		val[id] = tok
		tok += 1
	for x in adj[now]:
		if x != lst:
			subval[now] += val[x] * subval[x]

def solve():
	(N, X) = map(int, input().split())
	adj = [[] for i in range(N)]
	subval = [1 for i in range(N)]
	val = [0 for i in range(N)]
	for i in range(N - 1):
		(u, v) = map(int, input().split())
		u -= 1
		v -= 1
		adj[u].append(v)
		adj[v].append(u)
	dfs(0, adj, subval, val)
	print(subval[0] % mod * X % mod)
for _ in range(int(input())):
	solve()


import sys
sys.setrecursionlimit(10 ** 6)

def dfs(node, adj, parent, x):
	val = []
	for n in adj[node]:
		if n != parent:
			val.append(dfs(n, adj, node, x))
	ls = len(val)
	val.sort()
	rev = [i + 1 for i in range(ls)][::-1]
	total = x
	for i in range(ls):
		total += rev[i] * val[i]
	return total
t = int(input())
for _ in range(t):
	(n, x) = map(int, input().split())
	adj = [[] for _ in range(n + 1)]
	for i in range(1, n):
		(p, c) = map(int, input().split())
		adj[p].append(c)
		adj[c].append(p)
	sum = dfs(1, adj, 0, x)
	print(sum % 1000000007)


import sys
from os import path
if path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')

def dfs(tree: list, depth: list, visited, node: int) -> int:
	if visited[node]:
		return 0
	visited[node] = True
	if not tree[node]:
		depth[node] = 1
		return 1
	depth[node] = sum((dfs(tree, depth, visited, x) for x in tree[node])) + 1
	return depth[node]

def put_values(tree: list, value: list, node: int) -> None:
	x = value[node]
	children: list = tree[node]
	for child in children:
		value[child] = x
		put_values(tree, value, child)
	child_with_value = [(value[child], child) for child in children]
	child_with_value.sort(reverse=True)
	for (index, (_, child)) in enumerate(child_with_value):
		value[child] = (index + 1) * value[child]
	value[node] = sum((value[child] for child in children)) + x

def put_values_with_stack(tree: list, value: list, node: int) -> None:
	x = value[node]
	stack = [node]
	visited = [False for _ in range(len(value))]
	while stack:
		node = stack.pop()
		children: list = tree[node]
		if children:
			if not visited[node]:
				visited[node] = True
				stack.append(node)
				stack += children
			else:
				child_with_value = [(value[child], child) for child in children]
				child_with_value.sort(reverse=True)
				for (index, (_, child)) in enumerate(child_with_value):
					value[child] = (index + 1) * value[child]
				value[node] = sum((value[child] for child in children)) + x
		else:
			value[node] = x

def create_proper_tree(tree, visited, node) -> None:
	queue = [node]
	while queue:
		node = queue.pop()
		visited[node] = True
		to_remove = []
		for child in tree[node]:
			if visited[child]:
				to_remove.append(child)
				continue
		for x in to_remove:
			tree[node].remove(x)
		for child in tree[node]:
			queue.append(child)

def test_memory():
	n = 300000
	tree = [[] for _ in range(n + 1)]
	for i in range(1, n):
		tree[i].append(i + 1)
		tree[i + 1].append(i)
	print(sys.getsizeof(tree))
	visited = [False for _ in range(2 * n + 1)]
	create_proper_tree(tree, visited, 1)
	value = [0 for _ in range(2 * n + 1)]
	put_values_with_stack(tree, value, 1)
t = int(input())
while t != 0:
	t -= 1
	(n, x) = (int(x) for x in input().split())
	tree = [[] for _ in range(2 * n + 1)]
	value = [0 for _ in range(2 * n + 1)]
	visited = [False for _ in range(2 * n + 1)]
	for _ in range(n - 1):
		(u, v) = (int(x) for x in input().split())
		tree[u].append(v)
		tree[v].append(u)
	value[1] = x
	visited = [False for _ in range(n + 1)]
	try:
		create_proper_tree(tree, visited, 1)
		put_values_with_stack(tree, value, 1)
		print(value[1] % 1000000007)
	except:
		raise
		print(1)


import sys

def cal(adj, n):
	val = [0] * n
	wgt = [1] * n
	stk = [[-1, 0, adj[0]]]
	vst = [False] * n
	while len(stk) > 0:
		this = stk[-1]
		prev = this[0]
		curr = this[1]
		chld = this[2]
		if not vst[curr]:
			vst[curr] = True
			dive = False
			for node in chld:
				if node == prev:
					continue
				stk.append([curr, node, adj[node]])
				dive = True
			if dive:
				continue
		wgts = []
		for node in chld:
			if node == prev:
				continue
			wgts.append([node, wgt[node]])
		wgts.sort(reverse=True, key=lambda x: x[1])
		cnt = 1
		for i in wgts:
			val[i[0]] = cnt
			cnt += 1
		for node in chld:
			if node == prev:
				continue
			wgt[curr] += val[node] * wgt[node]
		stk.pop()
	return wgt[0]

def solution(inp):
	mod = 10 ** 9 + 7
	pos = 1
	for i in range(int(inp[0])):
		(n, x) = map(int, inp[pos].split())
		pos += 1
		adj = dict()
		for j in range(pos, pos + n - 1):
			(u, v) = map(int, inp[j].split())
			u -= 1
			v -= 1
			if u in adj:
				adj[u].append(v)
			else:
				adj[u] = [v]
			if v in adj:
				adj[v].append(u)
			else:
				adj[v] = [u]
		pos += n - 1
		ans = cal(adj, n) % mod * x % mod
		print(ans)

def main():
	inp = sys.stdin.read().split('\n')
	solution(inp)
main()


import sys
sys.setrecursionlimit(10 ** 6)
for t in range(int(input())):
	(n, k) = map(int, input().split())
	adj = [[] for i in range(n + 100)]

	def addEdge(a, b):
		adj[a].append(b)
		adj[b].append(a)
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		addEdge(u, v)
	sub_val = [1] * (n + 100)
	value = [0] * (n + 100)

	def dfs(current, last):
		for i in adj[current]:
			if i == last:
				continue
			dfs(i, current)
		queue = []
		for i in adj[current]:
			if i == last:
				continue
			queue.append([sub_val[i], i])
		queue.sort(reverse=True)
		temp = 1
		for (i, j) in queue:
			value[j] += temp
			temp += 1
		for i in adj[current]:
			if i == last:
				continue
			sub_val[current] += value[i] * sub_val[i]
	dfs(1, -1)
	mod = 10 ** 9 + 7
	ans = sub_val[1] % mod * k % mod
	print(ans)
exit()


import sys
sys.setrecursionlimit(10 ** 6)

def traversal(node, parent):
	for x in edges[node]:
		if x != parent:
			traversal(x, node)
	child = []
	for x in edges[node]:
		if x != parent:
			child.append((sum_child[x], x))
	child.sort(reverse=True)
	cnt = 1
	for (_, idx) in child:
		child_val[idx] = cnt
		cnt += 1
	for x in edges[node]:
		if x != parent:
			sum_child[node] += child_val[x] * sum_child[x]
mod = 10 ** 9 + 7
T = int(input())
for _ in range(T):
	(N, X) = map(int, input().split())
	sum_child = [1] * N
	child_val = [0] * N
	edges = {}
	for i in range(N - 1):
		(u, v) = map(int, input().split())
		u = u - 1
		v = v - 1
		if u in edges:
			edges[u].append(v)
		else:
			edges[u] = [v]
		if v in edges:
			edges[v].append(u)
		else:
			edges[v] = [u]
	traversal(0, -1)
	ans = sum_child[0] * X
	print(ans % mod)


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

def addEdge(graph, u, v):
	graph[u].append(v)
	graph[v].append(u)

def method_1(val_node, val_under_node, graph, current, parent):
	arr = []
	for v in graph[current]:
		if v != parent:
			method_1(val_node, val_under_node, graph, v, current)
			arr.append((val_under_node[v], v))
		else:
			continue
	arr.sort(reverse=True)
	temp = 1
	for i in arr:
		val_node[i[1]] = temp
		temp = temp + 1
	for v in graph[current]:
		if v != parent:
			val_under_node[current] = val_under_node[current] + val_node[v] * val_under_node[v]
t = int(input())
for _ in range(t):
	(n, x) = map(int, input().split())
	graph = defaultdict(list)
	val_node = [0] * n
	val_under_node = [1] * n
	for __ in range(n - 1):
		(u, v) = map(int, input().split())
		addEdge(graph, u - 1, v - 1)
	method_1(val_node, val_under_node, graph, 0, -1)
	print(val_under_node[0] * x % (10 ** 9 + 7))


from collections import defaultdict, deque
PRIME = int(1000000000.0 + 7)

def BuildTree(root, adjacencies):
	parents = {}
	children = defaultdict(list)
	queue = deque([(root, None)])
	while len(queue) > 0:
		(node, parent) = queue.popleft()
		parents[node] = parent
		children[parent].append(node)
		for nbr in adjacencies[node]:
			if nbr != parent:
				queue.append((nbr, node))
	return (parents, children)

def PostOrderTraversal(children):
	output = deque()
	stack = [1]
	while len(stack) > 0:
		node = stack.pop()
		output.appendleft(node)
		if node not in children:
			continue
		for child in children[node]:
			stack.append(child)
	return output

def Traverse(traversal, parents):
	values = defaultdict(list)
	for node in traversal:
		total = 1
		if node in values:
			r = sorted(values[node], reverse=True)
			for (index, val) in enumerate(r):
				total = total + (index + 1) * val
		values[parents[node]].append(total)
	return values[None][0]

def main():
	T = int(input())
	for _ in range(T):
		(N, X) = [int(y) for y in input().split()]
		adjacencies = defaultdict(list)
		for _ in range(N - 1):
			(u, v) = [int(y) for y in input().split()]
			adjacencies[u].append(v)
			adjacencies[v].append(u)
		(parents, children) = BuildTree(1, adjacencies)
		traversal = PostOrderTraversal(children)
		minSum = Traverse(traversal, parents)
		print(X * minSum % PRIME)
main()


t = int(input())
import sys
sys.setrecursionlimit(500000)
mod = 10 ** 9 + 7
for _ in range(t):
	(n, x) = map(int, input().strip().split())
	nodes = [list() for i in range(n)]
	for i in range(n - 1):
		(a, b) = map(int, input().strip().split())
		nodes[a - 1].append(b - 1)
		nodes[b - 1].append(a - 1)
	visited = set()

	def recurse(ind):
		visited.add(ind)
		temp = []
		for child in nodes[ind]:
			if child not in visited:
				temp.append(recurse(child))
		temp.sort(reverse=True)
		z = 1
		i = 0
		val = 0
		while i < len(temp):
			some = z * temp[i]
			val = val + some
			i += 1
			z += 1
		return val + 1
	ans = recurse(0)
	print(ans % mod * (x % mod) % mod)


if 1 == 1:
	import sys
	sys.setrecursionlimit(10 ** 9)

	class trees:
		k = 0
		visited = 0
		vals = 0
		muls = 0

	def DFS(node, tree, first=-1):
		MOD = 10 ** 9 + 7
		for i in range(len(tree[node])):
			if tree[node][i] != first:
				DFS(tree[node][i], tree, node)
		a = list()
		for i in range(len(tree[node])):
			if tree[node][i] != first:
				a.append(trees.vals[tree[node][i]])
		a.sort(reverse=True)
		for k in range(len(a)):
			trees.vals[node] = trees.vals[node] + (k + 1) * a[k]
		a.clear()
	for _ in range(int(input())):
		MOD = 10 ** 9 + 7
		(n, x) = map(int, input().split())
		tree = [[] for _ in range(n + 1)]
		for i in range(n - 1):
			(u, v) = map(int, input().split())
			tree[u].append(v)
			tree[v].append(u)
		trees.visited = [True for _ in range(n + 1)]
		trees.vals = [x for _ in range(n + 1)]
		DFS(1, tree)
		print(trees.vals[1] % MOD)


from collections import deque
import time

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

def transverse(child, n, x, count_child, parent, level):
	p = 10 ** 9 + 7
	value = [0] * (n + 1)
	visit = [False] * (n + 1)
	queue = deque()
	queue.append((1, 1))
	value[1] = x
	while queue:
		s = queue.popleft()
		x = value[s[0]]
		visit[s[0]] == True
		i = 1
		for vertice in sorted(child[s[0]], key=lambda x: (count_child[x], n + 1 - level[x]), reverse=True):
			if visit[vertice] == False and vertice != s[1]:
				value[vertice] = x * i
				i += 1
				visit[vertice] = True
				queue.append((vertice, s[0]))
	print(sum(value) % p)

def bfs(node, tree, n):
	count_child = [0] * (n + 1)
	count_child[1] = -1
	ans = [0] * (n + 1)
	vis = [0] * (n + 1)
	qu = deque()
	qu.append((node, 1))
	while qu:
		p = qu.popleft()
		ans[p[0]] = p[1]
		count_child[p[1]] += 1
		vis[p[0]] = True
		for child in tree[p[0]]:
			if not vis[child]:
				qu.append((child, p[0]))
	return (count_child, ans)

def dfs(node, par):
	for x in child[node]:
		if x == par:
			continue
		dfs(x, node)
	c = []
	for x in child[node]:
		if x != par:
			c.append((sub_val[x], x))
	c.sort(reverse=True)
	k = 1
	for (m, n) in c:
		value[n] += k
		k += 1
	for x in child[node]:
		if x != par:
			sub_val[node] += value[x] * sub_val[x]
try:
	start = time.time()
	t = int(input())
	p = 10 ** 9 + 7
	while t:
		t -= 1
		child = [[] for i in range(4)]
		(n, x) = map(int, input().split())
		child = [[] for i in range(n + 1)]
		sub_val = [1] * (n + 1)
		value = [0] * (n + 1)
		level = [1] * (n + 1)
		for i in range(n - 1):
			(u, v) = map(int, input().split())
			child[u].append(v)
			child[v].append(u)
		all_children = [0] * (n + 1)
		all_children[1] = n - 1
		(immed_child, parent) = bfs(1, child, n)
		if immed_child.count(1) >= n // 2:
			all_child = [0] * (n + 1)
			for i in range(n, 1, -1):
				level[parent[i]] = max(level[parent[i]], level[i] + 1)
				if immed_child[i] == 0:
					all_child[parent[i]] = all_child[parent[i]] + immed_child[i] + 1
				else:
					all_child[parent[i]] = all_child[parent[i]] + all_child[i] + 1
			transverse(child, n, x, all_child, parent, level)
		else:
			dfs(1, 1)
			print(sub_val[1] % p * x % p)
	end = time.time()
except:
	pass


mod = 10 ** 9 + 7
import sys
sys.setrecursionlimit(300000)

class Tree:

	def __init__(self, n):
		self.nodes = []
		for i in range(n + 1):
			self.nodes.append([])

def checkUtil(t, x, parent):
	k = []
	sum = 1
	for i in t.nodes[x]:
		if i != parent:
			if len(t.nodes[i]) > 1:
				k.append(checkUtil(t, i, x))
			else:
				k.append(1)
	k.sort(reverse=True)
	for i in range(1, len(k) + 1):
		sum += i * k[i - 1]
	return sum

def check(t, x):
	k = []
	sum = 1
	for i in t.nodes[x]:
		if len(t.nodes[i]) > 1:
			k.append(checkUtil(t, i, x))
		else:
			k.append(1)
	k.sort(reverse=True)
	for i in range(1, len(k) + 1):
		sum += i * k[i - 1]
	return sum
for _ in range(int(input())):
	(n, x) = map(int, input().split())
	t = Tree(n)
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		t.nodes[u].append(v)
		t.nodes[v].append(u)
	y = check(t, 1) % mod
	res = x * y % mod
	print(res)


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

	def sol(r):
		(ans, m) = (1, len(r))
		for kk in range(m - 1, -1, -1):
			ans = ans + (m - kk) * r[kk]
		return ans

	def trav(g, a, b, l):
		for jj in g[a]:
			if b != jj:
				l.append(trav(g, jj, a, []))
		return sol(sorted(l))
	for ii in range(int(input())):
		(n, x) = map(int, input().split())
		t = defaultdict(list)
		for jj in range(n - 1):
			(u, v) = map(int, input().split())
			t[u].append(v)
			t[v].append(u)
		res = x * (trav(t, 1, -1, []) % (10 ** 9 + 7)) % (10 ** 9 + 7)
		print(res)
except:
	pass


import sys
sys.setrecursionlimit(10 ** 6)

def solve():
	(n, m) = map(int, input().split())
	answer = [1] * (n + 1)
	multiplier = [0] * (n + 1)
	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)

	def dfs(root, t=-1):
		for node in adj[root]:
			if node == t:
				continue
			dfs(node, root)
		ch = []
		for node in adj[root]:
			if node != t:
				ch.append((answer[node], node))
		ch.sort(reverse=True)
		temp = 1
		for (a, b) in ch:
			multiplier[b] = temp
			temp += 1
		for node in adj[root]:
			if node != t:
				answer[root] += multiplier[node] * answer[node]
	dfs(1)
	print(answer[1] * m % (10 ** 9 + 7))
for _ in range(int(input())):
	solve()


from collections import defaultdict
import sys
sys.setrecursionlimit(110000)
M = 10 ** 9 + 7

class Edge:

	def __init__(self, u, v):
		self.u = u
		self.v = v

class Graph:

	def __init__(self, V, val):
		self.V = V
		self.nodes = defaultdict(list)

	def addEdge(self, u, v):
		self.nodes[u].append(Edge(u, v))

	def adj(self, u):
		return self.nodes[u]

def calculateChild(graph, u, visited):
	visited.add(u)
	if len(graph.adj(u)) == 0:
		return 1
	l = []
	for edge in graph.adj(u):
		if edge.v not in visited:
			l.append(calculateChild(graph, edge.v, visited))
	summ = 0
	l.sort(reverse=True)
	for (count, i) in enumerate(l, 1):
		summ = summ + i * count
	summ += 1
	return summ
t = int(input())
for i in range(t):
	(n, x) = list(map(int, input().split()))
	graph = Graph(n, x)
	for i in range(n - 1):
		(u, v) = list(map(int, input().split()))
		graph.addEdge(u, v)
		graph.addEdge(v, u)
	visited = set()
	ans = calculateChild(graph, 1, visited)
	print(ans * x % M)


import sys

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

def iinput():
	return int(input())

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

def get_list():
	return list(map(int, sys.stdin.readline().strip().split()))
mod = 10 ** 9 + 7
sys.setrecursionlimit(10 ** 6)

def func(present, parent):
	for i in d[present]:
		if i != parent:
			func(i, present)
	li = [[l1[x], x] for x in d[present] if x != parent]
	li.sort(reverse=True)
	count = 1
	for item in li:
		(l2i, xi) = item
		l2[xi] = count
		count += 1
	for i in d[present]:
		if i != parent:
			l1[present] += l2[i] * l1[i]
t = iinput()
while t > 0:
	(n, x) = rinput()
	d = {}
	for i in range(1, n + 1):
		d[i] = []
	for _ in range(n - 1):
		(a, b) = rinput()
		d[a].append(b)
		d[b].append(a)
	for i in d:
		d[i].sort()
	l1 = [1] * (n + 1)
	l2 = [0] * (n + 1)
	func(1, -1)
	s = l1[1] % mod * x % mod
	print(s % mod)
	t -= 1


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

def calcSum(adj, s, l=-1):
	temp = []
	for z in adj[s]:
		if z != l:
			bisect.insort(temp, calcSum(adj, z, s))
	length = len(temp)
	return 1 + sum([i * temp[length - i] for i in range(1, length + 1)])
for _ in range(int(sys.stdin.readline())):
	(n, x) = map(int, sys.stdin.readline().split())
	adj = defaultdict(list)
	for i in range(n - 1):
		(u, v) = map(int, sys.stdin.readline().split())
		adj[u].append(v)
		adj[v].append(u)
	print(calcSum(adj, 1) * x % mod)


import sys
sys.setrecursionlimit(400000)

def _recursion(Adj, lens, Nodes, node):
	for i in range(lens[node]):
		Nodes[node].add_child(Nodes[Adj[node][i]])
		Adj[Adj[node][i]].remove(node)
		lens[Adj[node][i]] -= 1
		_recursion(Adj, lens, Nodes, Adj[node][i])

def recursion(node):
	if node.isleaf:
		return 1
	Sums = []
	for child in node.children:
		Sums.append(recursion(child))
	Sums.sort(reverse=True)
	Sum = 1
	for i in range(node.length):
		Sum += Sums[i] * (i + 1)
	return Sum

class Node:

	def __init__(self):
		self.children = []
		self.length = 0
		self.isleaf = True

	def add_child(self, node):
		self.children.append(node)
		self.length += 1
		self.isleaf = False
t = int(input())
assert 1 <= t <= 15
for _ in range(t):
	(n, x) = tuple(map(int, input().split()))
	assert 2 <= n <= 300000
	assert 1 <= x <= 1000000000
	Nodes = [Node() for i in range(n)]
	Adj = [[] for i in range(n)]
	lens = [0 for i in range(n)]
	for i in range(n - 1):
		(u, v) = tuple(map(int, input().split()))
		assert 1 <= u <= n and 1 <= v <= n and (u != v)
		Adj[u - 1].append(v - 1)
		lens[u - 1] += 1
		Adj[v - 1].append(u - 1)
		lens[v - 1] += 1
	_recursion(Adj, lens, Nodes, 0)
	print(recursion(Nodes[0]) * x % 1000000007)


from collections import defaultdict
import sys
sys.setrecursionlimit(300005)
M = 10 ** 9 + 7
t = int(input())
for _ in range(t):
	(n, x) = [int(ele) for ele in input().split()]
	dic = defaultdict(list)
	for i in range(n - 1):
		(u, v) = [int(ele) for ele in input().split()]
		dic[u].append(v)
		dic[v].append(u)
	values = [0] * (n + 1)
	values[1] = x
	nodes = [0] * (n + 1)

	def tmp(s):
		ans = 0
		for child in dic[s]:
			ans += tmp(child)
		nodes[s] = ans + 1
		return nodes[s]

	def rec(s, x):
		values[s] = x
		tmp = 0
		for child in sorted(dic[s], key=lambda x: -nodes[x]):
			tmp = (tmp + x) % M
			rec(child, tmp)

	def f(s, last=-1):
		child_ans_list = []
		for child in dic[s]:
			if child == last:
				continue
			child_ans_list.append(f(child, s))
		child_ans_list.sort(reverse=True)
		tmp = 0
		res = 1
		for ch in child_ans_list:
			tmp = (tmp + 1) % M
			res = res + ch * tmp
		return res
	print(x * f(1) % M)


import sys
import os.path
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
depth = 1000005
mod = 1000000007
sys.setrecursionlimit(depth)

def dfs(u, p):
	vals = []
	for v in adj[u]:
		if v != p:
			vals.append(dfs(v, u))
	(res, i) = (1, 1)
	vals.sort(reverse=True)
	for e in vals:
		res += e * i
		i += 1
	return res
for _ in range(int(input())):
	(n, x) = map(int, input().split())
	adj = [[] for _ in range(n + 1)]
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		adj[u].append(v)
		adj[v].append(u)
	ans = dfs(1, 1) % mod
	ans = ans * x % mod
	print(ans)


from sys import stdin, setrecursionlimit as srl
ip = stdin.readline
srl(int(1000000.0))
for _ in range(int(ip())):
	(n, x) = map(int, ip().split())
	graph = [[] for _ in range(n + 1)]
	for _ in range(n - 1):
		(u, v) = map(int, ip().split())
		graph[u].append(v)
		graph[v].append(u)

	def ans(root, last):
		rank = [ans(child, root) for child in graph[root] if not child == last]
		rank.sort(reverse=True)
		return sum(((i + 1) * rank[i] for i in range(len(rank)))) + 1
	print(ans(1, -1) * x % (int(1000000000.0) + 7))