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

You are given a tree with $N$ nodes numbered from $1$ to $N$. A set $S$ of nodes is called valid if there exist two vertices $u$ and $v$ (possibly, $u=v$) such that every node in $S$ lies on the simple path from $u$ to $v$.

Count the number of valid sets modulo $10^{9}+7$. Two sets are different if one node is included in one set and not in the other. If there are multiple pairs $(u, v)$ making a set valid, that set is still only counted once.

------ Input ------
The first line contains an integer $T$, the number of test cases. Then the test cases follow. 
Each test case contains $N$ lines of input.
The first line contains a single integer $N$, the number of tree nodes. 
Each of the next $N-1$ lines contains two space-separated integers $u$ and $v$ representing an edge between nodes $u$ and $v$. 

------ Output ------
For each test case, output in a single line the number of valid sets modulo $10^{9} + 7$.

------ Constraints  ------
$1 ≤ T ≤ 50$
$1 ≤ N ≤ 10^{5}$
$1 ≤ u, v ≤ N$
Sum $N$ over all testcases is at most $5\cdot 10^{5}$.
The given input is a valid tree.

------ Subtasks ------
Subtask #1 (20 points): 
$1 ≤ T ≤ 10$
$1 ≤ N ≤ 3\cdot 10^{3}$

Subtask #2 (80 points): Original Constraints

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

4

1 2

3 1

2 4

4

1 2

2 3

2 4
----- Sample Output 1 ------ 
15

13
----- explanation 1 ------ 
Test Case $1$: Every non-empty set is valid.

Test Case $2$: The valid sets are $\{1\}$, $\{2\}$, $\{3\}$, $\{4\}$, $\{1, 2\}$, $\{1, 3\}$, $\{1, 4\}$, $\{2, 3\}$, $\{2, 4\}$, $\{3, 4\}$, $\{1, 2, 3\}$,  $\{1, 2, 4\}$, $\{2, 3, 4\}$.

Difficulty: HARD
Tags: Graph algorithms

Graph traversal

Combinatorics

Mathematics

Starter code:

Solutions:
import sys
sys.setrecursionlimit(10 ** 9)
try:
	t = int(input())

	def dfs(graph, node, ans, v, anc):
		v[node] = 1
		ans[0] += 1
		for child in graph[node]:
			if child == anc:
				continue
			dfs(graph, child, ans, v, node)
			ans[0] += int(v[node] * v[child] % (10 ** 9 + 7))
			v[node] += int(2 * v[child] % (10 ** 9 + 7))
			v[node] %= 10 ** 9 + 7
			ans[0] %= 10 ** 9 + 7
			v[node] = int(v[node])
			ans[0] = int(ans[0])
	while t > 0:
		n = int(input())
		if n == 1:
			print(1)
			t -= 1
			continue
		graph = dict()
		for ind in range(n - 1):
			(u, v) = tuple(map(int, input().split()))
			if u not in graph:
				graph[u] = [v]
			else:
				graph[u].append(v)
			if v not in graph:
				graph[v] = [u]
			else:
				graph[v].append(u)
		ans = [0]
		v1 = dict()
		dfs(graph, 1, ans, v1, 1)
		print(int(ans[0]))
		t -= 1
except EOFError as e:
	print(e)


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

def dfs(node, tree, visited, final):
	visited[node] = True
	child = tree[node]
	temp = []
	ret = 0
	for i in child:
		if visited[i] == False:
			ans = dfs(i, tree, visited, final)
			temp.append(ans)
			ret += 2 * ans
	ret += 1
	s = 0
	for i in temp:
		s += i
	for i in temp:
		s -= i
		final[0] = (final[0] + 2 * s * i % mod) % mod
	return ret

def solve(king, tree):
	visited = [False for x in range(len(tree))]
	visited[king] = True
	child = tree[king]
	temp = []
	ret = 0
	mat = [0]
	for i in child:
		ans = dfs(i, tree, visited, mat)
		temp.append(ans)
		ret += 2 * ans
	ret += 1
	final = mat[0]
	s = 0
	for i in temp:
		s += i
	for i in temp:
		s -= i
		final = (final + 2 * s * i % mod) % mod
	final = (final + ret % mod) % mod
	print(final)
t = int(input())
for test in range(t):
	n = int(input())
	tree = [[] for x in range(n + 1)]
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		tree[u].append(v)
		tree[v].append(u)
	solve(1, tree)


import sys
sys.setrecursionlimit(10 ** 6)
test = int(input())
mex = 100001
mod = 10 ** 9 + 7
v = [[] for _ in range(mex)]
dp = [[] for _ in range(mex)]

def dfs(n, p):
	dp[n] = [1, 0]
	sum1 = 0
	childs = []
	for child in v[n]:
		if child != p:
			dfs(child, n)
			dp[n][0] += dp[child][0] * 2
			dp[n][0] %= mod
			sum1 += dp[child][0]
			sum1 %= mod
			childs.append(dp[child][0])
	for val in childs:
		dp[n][1] += (sum1 - val) * val % mod
		dp[n][1] %= mod
for i in range(test):
	n = int(input())
	for i in range(1, n + 1):
		v[i].clear()
		dp[i].clear()
	for i in range(n - 1):
		(a, b) = map(int, input().split())
		v[a].append(b)
		v[b].append(a)
	dfs(1, 0)
	ans = 0
	for i in range(1, n + 1):
		ans += dp[i][1]
		ans %= mod
	ans += dp[1][0]
	ans %= mod
	print(ans)


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

def dfs(now, x):
	(l1[now], l2[now]) = (1, 1)
	cnt = 0
	for i in range(len(ajl[now])):
		y = ajl[now][i]
		if x != y:
			dfs(y, now)
			l1[now] += 2 * l1[y]
			l2[now] += l2[y] + l1[y]
			cnt += l1[y]
	for i in range(len(ajl[now])):
		y = ajl[now][i]
		if x != y:
			l2[now] += l1[y] * (cnt - l1[y])
t = int(input())
for _ in range(t):
	n = int(input())
	ajl = [[] for i in range(n + 1)]
	for _ in range(n - 1):
		(u, v) = map(int, input().split())
		ajl[u].append(v)
		ajl[v].append(u)
	l1 = [0] * (n + 1)
	l2 = [0] * (n + 1)
	dfs(1, 1)
	print(l2[1] % MOD)


ans = 0
v = []
dp = []
tot = []
mod = 10 ** 9 + 7
import sys
sys.setrecursionlimit(10 ** 6)

def dfs(cur, par):
	dp[cur] = 1
	tot[cur] = 1
	sum = 0
	cnt = 0
	for i in range(len(v[cur])):
		node = v[cur][i]
		if node != par:
			dfs(node, cur)
			dp[cur] += 2 * dp[node] % mod
			dp[cur] %= mod
			cnt += 1
			tot[cur] += tot[node]
			tot[cur] %= mod
			tot[cur] += dp[node]
			tot[cur] %= mod
			sum += dp[node]
	for i in range(len(v[cur])):
		node = v[cur][i]
		if node != par:
			tot[cur] += dp[node] * (sum - dp[node] + mod) % mod
			tot[cur] %= mod
for _ in range(int(input())):
	ans = 0
	n = int(input())
	v = [[] for i in range(n + 1)]
	dp = [0 for i in range(n + 1)]
	tot = [0 for i in range(n + 1)]
	for i in range(n - 1):
		(l, r) = [int(i) for i in input().split()]
		v[l].append(r)
		v[r].append(l)
	dfs(1, 1)
	ans = tot[1] % mod
	print(ans)
	dp = []
	v = []
	tot = []


import sys
sys.setrecursionlimit(1000000000)
input = sys.stdin.readline
mod = 1000000007

def dfs(ind, rap):
	(arr[ind], arr1[ind], s, flag) = (1, 1, 0, 0)
	a = len(v[ind])
	for i in range(a):
		nd = v[ind][i]
		if nd != rap:
			dfs(nd, ind)
			arr[ind] = (arr[ind] + 2 * arr[nd] % mod) % mod
			flag += 1
			arr1[ind] = ((arr1[ind] + arr1[nd]) % mod + arr[nd]) % mod
			s += arr[nd]
	for i in range(a):
		nd = v[ind][i]
		if nd != rap:
			arr1[ind] += arr[nd] * (s - arr[nd] + mod) % mod % mod
			arr1[ind] %= mod
t = int(input())
while t:
	t -= 1
	ans = 0
	n = int(input())
	v = [[] for x in range(n + 1)]
	arr = [0] * (n + 1)
	arr1 = [0] * (n + 1)
	for i in range(1, n):
		(l, r) = [int(x) for x in input().split()]
		v[l].append(r)
		v[r].append(l)
	dfs(1, 1)
	print(arr1[1] % mod)


import sys
sys.setrecursionlimit(1000000000)
mod = 1000000007

def depth_first(c, p):
	(s, dp_second[c], dp_first[c], cnt) = (0, 1, 1, 0)
	l = len(val[c])
	for i in range(l):
		node = val[c][i]
		if node != p:
			depth_first(node, c)
			dp_first[c] = (dp_first[c] + 2 * dp_first[node] % mod) % mod
			cnt += 1
			dp_second[c] += dp_second[node]
			dp_second[c] %= mod
			dp_second[c] += dp_first[node]
			dp_second[c] %= mod
			s += dp_first[node]
	for i in range(len(val[c])):
		node = val[c][i]
		if node != p:
			dp_second[c] += dp_first[node] * (s - dp_first[node] + mod) % mod % mod
			dp_second[c] %= mod
for _ in range(int(input())):
	ans = 0
	n = int(input())
	val = []
	dp_first = [0] * (n + 1)
	dp_second = [0] * (n + 1)
	for i in range(n + 1):
		val.append([])
	for i in range(1, n):
		(l, r) = [int(x) for x in input().split()]
		val[l].append(r)
		val[r].append(l)
	depth_first(1, 1)
	print(dp_second[1] % mod)


import sys
sys.setrecursionlimit(1000000000)
mod = 1000000007
v = [[]]
dp = []
dp1 = []

def dfs(cur, par):
	dp[cur] = 1
	dp1[cur] = 1
	sum1 = 0
	cnt = 0
	for i in range(len(v[cur])):
		node = v[cur][i]
		if node != par:
			dfs(node, cur)
			dp[cur] += 2 * dp[node] % mod
			dp[cur] %= mod
			cnt += 1
			dp1[cur] += dp1[node]
			dp1[cur] %= mod
			dp1[cur] += dp[node]
			dp1[cur] %= mod
			sum1 += dp[node]
	for i in range(len(v[cur])):
		node = v[cur][i]
		if node != par:
			dp1[cur] += dp[node] * (sum1 - dp[node] + mod) % mod % mod
			dp1[cur] %= mod
t = int(input())
for _ in range(t):
	ans = 0
	n = int(input())
	v = []
	dp = []
	dp1 = []
	for i in range(n + 1):
		v.append([])
		dp.append(0)
		dp1.append(0)
	for i in range(1, n):
		(l, r) = [int(x) for x in input().split()]
		v[l].append(r)
		v[r].append(l)
	dfs(1, 1)
	print(dp1[1] % mod)


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

def add(a, b):
	return (a % mod + b % mod) % mod

def mul(a, b):
	return a % mod * b % mod % mod

def sub(a, b):
	return (a % mod - b % mod + mod) % mod

def dfs(node, prev):
	for adjacents in childs[node]:
		if adjacents != prev:
			dfs(adjacents, node)
	temp = 0
	for adjacents in childs[node]:
		if adjacents != prev:
			dp[node] = add(dp[node], 2 * dp[adjacents])
			subtree_values[node] = add(add(subtree_values[adjacents], dp[adjacents]), subtree_values[node])
			temp += dp[adjacents]
	for adjacents in childs[node]:
		if adjacents != prev:
			subtree_values[node] += mul(dp[adjacents], sub(temp, dp[adjacents]))
	subtree_values[node] %= mod
for _ in range(int(input())):
	n = int(input())
	childs = [[] for i in range(n + 1)]
	for i in range(n - 1):
		(a, b) = map(int, input().strip().split())
		childs[a].append(b)
		childs[b].append(a)
	dp = [1] * (n + 1)
	subtree_values = [1] * (n + 1)
	dfs(1, -1)
	print(subtree_values[1] % mod)


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

def findProductSum(A, n):
	array_sum = 0
	for i in range(0, n, 1):
		array_sum = array_sum + A[i]
	array_sum_square = array_sum * array_sum
	individual_square_sum = 0
	for i in range(0, n, 1):
		individual_square_sum += A[i] * A[i]
	return (array_sum_square - individual_square_sum) // 2 % mod

def traverse(par, node):
	if len(adj[node]) == 1 and node != 1:
		return 1
	arr = []
	for j in adj[node]:
		if j == par:
			continue
		rn = traverse(node, j)
		arr.append(rn)
	if len(arr) > 1:
		sidew.append(findProductSum(arr, len(arr)) * 2 % mod)
	return (sum(arr) * 2 + 1) % mod
for t in range(int(input())):
	N = int(input())
	adj = defaultdict(list)
	sidew = []
	if N == 1:
		print(1)
	else:
		for i in range(N - 1):
			(a, b) = map(int, input().split())
			adj[a].append(b)
			adj[b].append(a)
		ans = traverse(1, 1)
		print((ans + sum(sidew)) % mod)


import sys
sys.setrecursionlimit(10 ** 6)

def solve():
	n = int(input())
	adj = [[] for _ in range(n + 1)]
	aux = [1] * (n + 1)
	answer = [1] * (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):
		count = 0
		for node in adj[root]:
			if node == t:
				continue
			dfs(node, root)
			aux[root] += 2 * aux[node]
			answer[root] += aux[node] + answer[node]
			count += aux[node]
		for node in adj[root]:
			if node != t:
				answer[root] += (count - aux[node]) * aux[node]
	dfs(1)
	print(answer[1] % (10 ** 9 + 7))
for _ in range(int(input())):
	solve()


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

class Tree:

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

	def __dfs(self, cur, parent):
		self.val_final[cur] = 1
		s = 0
		for (i, v) in enumerate(self.adj[cur]):
			if v != parent:
				self.__dfs(v, cur)
				self.val_root[cur] += 2 * self.val_root[v] % M
				self.val_root[cur] %= M
				self.val_final[cur] += (self.val_final[v] + self.val_root[v]) % M
				self.val_final[cur] %= M
				s += self.val_root[v]
				s %= M
		for (i, v) in enumerate(self.adj[cur]):
			if v != parent:
				self.val_final[cur] += self.val_root[v] * ((s - self.val_root[v]) % M) % M
				self.val_final[cur] %= M

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

	def solve(self):
		self.__dfs(1, 0)
		return self.val_final[1]
for _ in range(int(input())):
	n = int(input())
	tree = Tree(n)
	for i in range(1, n):
		tree.insertEdge(*map(int, input().split()))
	print(tree.solve())


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

def depth(current, p):
	dpx[current] = 1
	t[current] = 1
	total = 0
	cnt = 0
	for i in range(len(graph[current])):
		node = graph[current][i]
		if node != p:
			depth(node, current)
			dpx[current] = dpx[current] + 2 * dpx[node] % 1000000007
			dpx[current] %= 1000000007
			cnt += 1
			t[current] += t[node]
			t[current] %= 1000000007
			t[current] += dpx[node]
			t[current] %= 1000000007
			total += dpx[node]
	for i in range(len(graph[current])):
		node = graph[current][i]
		if node != p:
			t[current] += dpx[node] * ((total - dpx[node] + 1000000007) % 1000000007) % 1000000007
			t[current] %= 1000000007
for _ in range(int(input())):
	n = int(input())
	graph = defaultdict(list)
	(dpx, t) = ([0] * (n + 1), [0] * (n + 1))
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		graph[u].append(v)
		graph[v].append(u)
	depth(1, 1)
	final = t[1]
	sys.stdout.write(str(final))
	sys.stdout.flush()
	print()


from sys import setrecursionlimit
setrecursionlimit(1000000)
mod = 1000000007

def dfs(node, root, dp, dp1, g):
	(dp[node], dp1[node]) = (1, 1)
	(sum_, cnt) = (0, 0)
	for curr in g[node]:
		if curr != root:
			dfs(curr, node, dp, dp1, g)
			dp[node] += 2 * dp[curr] % mod
			dp[node] = dp[node] % mod
			cnt += 1
			dp1[node] += dp1[curr]
			dp1[node] = dp1[node] % mod
			dp1[node] += dp[curr]
			dp1[node] %= mod
			sum_ += dp[curr]
	for curr in g[node]:
		if curr != root:
			dp1[node] += dp[curr] * (sum_ - dp[curr] + mod) % mod % mod
			dp1[node] %= mod
for _ in range(int(input())):
	n = int(input())
	g = [[] for _ in range(n + 1)]
	dp = [[] for _ in range(n + 1)]
	dp1 = [[] for _ in range(n + 1)]
	for _ in range(n - 1):
		(u, v) = map(int, input().split())
		g[u].append(v)
		g[v].append(u)
	dfs(1, 1, dp, dp1, g)
	ans = dp1[1] % mod
	print(ans)


import sys
sys.setrecursionlimit(10 ** 6)
for t in range(int(input())):
	n = int(input())
	adj = [[] for i in range(n + 10)]
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		adj[v].append(u)
		adj[u].append(v)
	dp = [0] * (n + 10)
	dp1 = [0] * (n + 10)

	def dfs(curr, par):
		dp[curr] = 1
		dp1[curr] = 1
		suma = 0
		count = 0
		for node in adj[curr]:
			if node != par:
				dfs(node, curr)
				dp[curr] += 2 * dp[node]
				count += 1
				dp1[curr] += dp1[node]
				dp1[curr] += dp[node]
				suma += dp[node]
		for node in adj[curr]:
			if node != par:
				dp1[curr] += dp[node] * (suma - dp[node])
	dfs(1, 1)
	mod = 10 ** 9 + 7
	print(dp1[1] % mod)


import sys
sys.setrecursionlimit(1000000)

def mgc(t, p):
	(dp[t], dp1[t]) = (1, 1)
	(sm, cnt) = (0, 0)
	for i in range(len(adj[t])):
		node = adj[t][i]
		if node != p:
			mgc(node, t)
			dp[t] += 2 * dp[node] % mod
			dp[t] %= mod
			cnt += 1
			dp1[t] += dp1[node]
			dp1[t] %= mod
			dp1[t] += dp[node]
			dp1[t] %= mod
			sm += dp[node]
	for i in range(len(adj[t])):
		node = adj[t][i]
		if node != p:
			dp1[t] += dp[node] * (sm - dp[node] + mod) % mod % mod
			dp1[t] %= mod
mod = 1000000007
for _ in range(int(input())):
	n = int(input())
	dp = [0] * (n + 1)
	adj = [[] for i in range(n + 1)]
	dp1 = [0] * (n + 1)
	for i in range(n - 1):
		(l, r) = map(int, input().split())
		adj[l].append(r)
		adj[r].append(l)
	mgc(1, 1)
	ans = dp1[1] % mod
	print(ans)


import sys
sys.setrecursionlimit(10 ** 8)
iparr = []
temparr = []
arrtree = []
Answer = 0
MOD = 1000000007

def DepthFirstSearch(kak, prac):
	(temparr[kak], arrtree[kak]) = (1, 1)
	loopsum = 0
	for i in range(len(iparr[kak])):
		TempValue = int(iparr[kak][i])
		if TempValue != prac:
			DepthFirstSearch(TempValue, kak)
			temparr[kak] += 2 * temparr[TempValue] % MOD
			temparr[kak] %= MOD
			arrtree[kak] += arrtree[TempValue]
			arrtree[kak] %= MOD
			arrtree[kak] += temparr[TempValue]
			arrtree[kak] %= MOD
			loopsum += temparr[TempValue]
	for i in range(len(iparr[kak])):
		TempValue = iparr[kak][i]
		if TempValue != prac:
			arrtree[kak] += temparr[TempValue] * ((loopsum - temparr[TempValue] + MOD) % MOD) % MOD
			arrtree[kak] %= MOD
for _ in range(int(sys.stdin.readline())):
	Answer = 0
	n = int(sys.stdin.readline())
	for i in range(n + 1):
		temparr.append(0)
		arrtree.append(0)
		iparr.append([])
	for i in range(n - 1):
		(x, y) = map(int, sys.stdin.readline().strip().split())
		iparr[x].append(y)
		iparr[y].append(x)
	DepthFirstSearch(1, 1)
	Answer = arrtree[1]
	sys.stdout.write(str(Answer) + '\n')
	arrtree.clear()
	iparr.clear()
	temparr.clear()


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

	def samepath(var, root, last):
		total[0] = (total[0] + var) % mod
		passon = 0
		for a in graph[root]:
			if a == last:
				continue
			varnext = 2 * (passon + var) % mod
			p = samepath(varnext, a, root)
			passon = (passon + 2 * p - 1) % mod
		return passon + 1
	samepath(1, 1, -1)
	print(total[0])


from sys import *
from collections import defaultdict as dd
from math import *
from bisect import *
setrecursionlimit(10 ** 8)

def sinp():
	return input()

def inp():
	return int(sinp())

def minp():
	return map(int, sinp().split())

def linp():
	return list(minp())

def strl():
	return list(sinp())

def pr(x):
	print(x)
mod = int(1000000000.0 + 7)

def dfs(x=1, y=1):
	dp[x] = 1
	ans[x] = 1
	res = 0
	for i in graph[x]:
		if i != y:
			dfs(i, x)
			dp[x] = (dp[x] + 2 * dp[i] % mod) % mod
			ans[x] = (ans[x] + ans[i]) % mod
			ans[x] = (ans[x] + dp[i]) % mod
			res += dp[i]
	for i in graph[x]:
		if i != y:
			ans[x] = (ans[x] + dp[i] * ((res - dp[i] + mod) % mod) % mod) % mod
for _ in range(inp()):
	n = inp()
	graph = dd(list)
	dp = [0 for i in range(n + 1)]
	ans = [0 for i in range(n + 1)]
	for i in range(n - 1):
		(u, v) = minp()
		graph[u].append(v)
		graph[v].append(u)
	dfs()
	pr(ans[1] % 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(current, parent):
	summ = 0
	for v in graph[current]:
		if v == parent:
			continue
		method_1(v, current)
		table[current] = table[current] + 2 * table[v]
		val[current] = val[current] + val[v] + table[v]
		summ = summ + table[v]
	for v in graph[current]:
		if v == parent:
			continue
		val[current] = val[current] + table[v] * abs(summ - table[v])
t = int(input())
for _ in range(t):
	n = int(input())
	graph = defaultdict(list)
	table = [1] * n
	val = [1] * n
	for __ in range(n - 1):
		(u, v) = map(int, input().split())
		addEdge(graph, u - 1, v - 1)
	method_1(0, -1)
	print(val[0] % (10 ** 9 + 7))


from collections import defaultdict
import sys
sys.setrecursionlimit(int(10000000.0))

def solve(root, graph, values, parent=None):
	for c in graph[root]:
		if c != parent:
			solve(c, graph, values, root)
	child_single_paths = sum((values[c][0] for c in graph[root] if c != parent))
	single_paths = (child_single_paths % int(1000000000.0 + 7) * 2 + 1) % int(1000000000.0 + 7)
	cross_paths = 0
	carry = 0
	running_sum = 0
	for i in range(len(graph[root])):
		c = graph[root][i]
		if c != parent:
			cross_paths += values[c][0] * (child_single_paths - values[c][0] - running_sum) % int(1000000000.0 + 7)
			running_sum += values[c][0]
	cross_paths = cross_paths % int(1000000000.0 + 7)
	carry = sum((values[c][1] for c in graph[root] if c != parent))
	values[root][0] = single_paths
	values[root][1] = (cross_paths * 2 + carry) % int(1000000000.0 + 7)
for _ in range(int(input())):
	N = int(input())
	graph = defaultdict(list)
	values = [[1, 0] for _ in range(N + 1)]
	for _ in range(N - 1):
		(u, v) = map(int, input().split())
		graph[u].append(v)
		graph[v].append(u)
	solve(1, graph, values)
	print((values[1][0] + values[1][1]) % int(1000000000.0 + 7))


import sys
sys.setrecursionlimit(10 ** 6)

class Scanner:

	def __init__(self):
		pass

	def readInt(self):
		return int(input())

	def readFloat(self):
		return map(float, input().split())

	def readList(self):
		return list(map(int, input().split()))

	def readString(self):
		return input()
sc = Scanner()
t = sc.readInt()
MAX = 100005
g = [[] for _ in range(MAX)]
through = [0 for _ in range(MAX)]
across = [0 for _ in range(MAX)]

def ways(u, parent):
	if parent != 0 and len(g[u]) == 1:
		through[u] = 1
		return
	v = []
	for child in g[u]:
		if child == parent:
			continue
		ways(child, u)
		through[u] += through[child] * 2
		v.append(through[child])
	sums = [0 for _ in range(len(v) + 1)]
	for i in reversed(range(len(v))):
		sums[i] = sums[i + 1] + v[i]
	for i in range(len(v)):
		across[u] += 2 * v[i] * sums[i + 1]
	through[u] += 1
for _ in range(t):
	n = sc.readInt()
	for _ in range(n - 1):
		(u, v) = map(int, input().split())
		g[u].append(v)
		g[v].append(u)
	ways(1, 0)
	ans = through[1]
	for i in range(1, n + 1):
		ans += across[i]
		g[i].clear()
		through[i] = 0
		across[i] = 0
	print(ans % 1000000007)


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

	def sol(g, l, i, res):
		(l[i], val, ar) = (True, 1, [])
		for jj in g[i]:
			if not l[jj]:
				(temp, res) = sol(g, l, jj, res)
				ar.append(temp)
				val = (val + temp * 2) % (10 ** 9 + 7)
		res = (res + prod(ar) + sum(ar)) % (10 ** 9 + 7)
		return (val, res)

	def prod(s):
		(sq, sq2) = (sum(s) ** 2, 0)
		for kk in range(len(s)):
			sq2 = (sq2 + s[kk] ** 2) % (10 ** 9 + 7)
		return (sq - sq2) % (10 ** 9 + 7)
	for ii in range(int(input())):
		n = int(input())
		(t, l, res, ans) = (defaultdict(list), defaultdict(bool), 0, n)
		for jj in range(n - 1):
			(u, v) = map(int, input().split())
			t[u].append(v)
			t[v].append(u)
		(x, y) = sol(t, l, 1, res)
		print((y + n) % (10 ** 9 + 7))
except:
	pass


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):
	for v in adj[u]:
		if v != p:
			dfs(v, u)
	s = 0
	for v in adj[u]:
		if v != p:
			dp1[u] = (dp1[u] + 2 * dp1[v]) % mod
			dp2[u] = (dp2[u] + dp2[v]) % mod
			s = (s + dp1[v]) % mod
	for v in adj[u]:
		if v != p:
			s = s - dp1[v]
			while s < 0:
				s += mod
			s %= mod
			dp2[u] = (dp2[u] + 2 * s * dp1[v] % mod) % mod
for _ in range(int(input())):
	n = int(input())
	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)
	dp1 = [1 for _ in range(n + 1)]
	dp2 = [0 for _ in range(n + 1)]
	dfs(1, 1)
	ans = (dp1[1] + dp2[1]) % mod
	print(ans)


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

def solve(graph, j, sub, high, x, mini):
	graph[j].sort(reverse=True, key=lambda x: (sub[x], -high[x]))
	for k in range(len(graph[j])):
		mini[graph[j][k]] = mini[j] * (k + 1)

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

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:
			dfs(node, current, g, dp, total)
			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]
	for i in range(len(g[current])):
		node = g[current][i]
		if node != parent:
			total[current] += dp[node] * ((s - dp[node] + mod) % mod) % mod
			total[current] %= mod

def SieveOfEratosthenes(n):
	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
from collections import defaultdict
for _ in range(int(input())):
	combination = 0
	n = int(input())
	n += 1
	dp = [0] * n
	total = [0] * n
	g = defaultdict(list)
	for i in range(n - 2):
		(u, v) = map(int, input().split())
		g[u].append(v)
		g[v].append(u)
	dfs(1, 1, g, dp, total)
	combination = total[1]
	print(combination % mod)


from collections import defaultdict as dd
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
mod = 1000000007

def dfs(cur, prev):
	prefix = [0 for i in range(len(tree[cur]))]
	j = 1
	for i in range(len(tree[cur])):
		if tree[cur][i] != prev:
			dfs(tree[cur][i], cur)
			dp[cur][1] += 2 * dp[tree[cur][i]][1]
			dp[cur][1] %= mod
			dp[cur][0] += dp[tree[cur][i]][1] + dp[tree[cur][i]][0]
			prefix[j] = prefix[j - 1]
			prefix[j] += dp[tree[cur][i]][1]
			prefix[j] %= mod
			j += 1
	k = 1
	for i in range(len(tree[cur])):
		if tree[cur][i] != prev:
			dp[cur][0] += 2 * dp[tree[cur][i]][1] * (prefix[j - 1] - prefix[k] + mod)
			dp[cur][0] %= mod
			k += 1
for _ in range(int(input())):
	n = int(input())
	tree = dd(list)
	dp = [[1, 1] for i in range(n + 1)]
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		tree[u].append(v)
		tree[v].append(u)
	tree[0].append(1)
	tree[1].append(0)
	dfs(1, 0)
	print(dp[1][0])


import sys
import math
sys.setrecursionlimit(1000000)

class Node:

	def __init__(self):
		self.adj = []
		self.val = 1
		self.visited = False

def dfs2(root):
	root.visited = True
	ch = []
	for i in range(len(root.adj)):
		if not root.adj[i].visited:
			ch.append(root.adj[i].val)
	temp = 0
	if len(ch) == 0 or len(ch) == 1:
		temp = 0
	else:
		s = 0
		p = 0
		for i in range(1, len(ch)):
			s += ch[i - 1]
			p = (p + ch[i] * s % 1000000007) % 1000000007
		temp = p * 2 % 1000000007
	ch1 = []
	for i in range(len(root.adj)):
		if not root.adj[i].visited:
			ch1.append(dfs2(root.adj[i]))
	return (temp + sum(ch1)) % 1000000007

def dfs(root):
	root.visited = True
	ch = []
	for i in range(len(root.adj)):
		if not root.adj[i].visited:
			ch.append(dfs(root.adj[i]))
	sm = sum(ch)
	root.val = (2 * sm + 1) % 1000000007
	return root.val
t = int(input())
for _ in range(t):
	n = int(input())
	tr = []
	for i in range(n):
		tr.append(Node())
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		tr[u - 1].adj.append(tr[v - 1])
		tr[v - 1].adj.append(tr[u - 1])
	ans = dfs(tr[0]) % 1000000007
	for i in range(n):
		tr[i].visited = False
	ans2 = dfs2(tr[0]) % 1000000007
	print((ans + ans2) % 1000000007)


import sys
sys.setrecursionlimit(20000000)
mod = 1000000007
dp = []
total = []
v = []

def dfs(curr, par):
	dp[curr] = 1
	total[curr] = 1
	sum = 0
	for i in range(len(v[curr])):
		node = v[curr][i]
		if node != par:
			dfs(node, curr)
			dp[curr] += 2 * dp[node] % mod
			dp[curr] %= mod
			total[curr] += total[node]
			total[curr] %= mod
			total[curr] += dp[node]
			total[curr] %= mod
			sum += dp[node]
	for i in range(len(v[curr])):
		node = v[curr][i]
		if node != par:
			total[curr] += dp[node] * ((sum - dp[node] + mod) % mod) % mod
			total[curr] %= mod
for _ in range(int(input())):
	ans = 0
	n = int(input())
	v = [[] for i in range(n + 1)]
	dp = [0 for i in range(n + 1)]
	total = [0 for i in range(n + 1)]
	for i in range(n - 1):
		(l, r) = map(int, input().split())
		v[l].append(r)
		v[r].append(l)
	dfs(1, 1)
	ans = total[1] % mod
	print(ans)
	dp.clear()
	v.clear()
	total.clear()


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

def dfs(cur, prev):
	dp[cur] = 1
	total[cur] = 1
	s = 0
	for data in graph[cur]:
		if data != prev:
			dfs(data, cur)
			dp[cur] += 2 * dp[data]
			total[cur] += total[data] + dp[data]
			s += dp[data]
	for data in graph[cur]:
		if data != prev:
			total[cur] += dp[data] * (s - dp[data])
for _ in range(int(input())):
	n = int(input())
	graph = defaultdict(list)
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		graph[u - 1].append(v - 1)
		graph[v - 1].append(u - 1)
	dp = [0] * (n + 5)
	total = [0] * (n + 5)
	dfs(0, -1)
	print(total[0] % mod)


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

def inp():
	return int(input())

def st():
	return input().rstrip('\n')

def lis():
	return list(map(int, input().split()))

def ma():
	return map(int, input().split())
global p, res
p = 10 ** 9 + 7

def dfs(cur, pa, deg, dp, val):
	global p
	loc = 0
	for i in deg[cur]:
		if i != pa:
			dfs(i, cur, deg, dp, val)
			dp[cur] += 2 * dp[i] % p
			val[cur] += (val[i] + dp[i]) % p
			loc += dp[i]
			dp[cur] %= p
			val[cur] %= p
	for i in deg[cur]:
		if i != pa:
			val[cur] += dp[i] * (loc - dp[i]) % p
			val[cur] %= p
t = inp()
while t:
	t -= 1
	n = inp()
	res = pow(2, n, p) - 1
	deg = [[] for i in range(n + 1)]
	for i in range(n - 1):
		(x, y) = ma()
		deg[x].append(y)
		deg[y].append(x)
	dp = [1 for i in range(n + 1)]
	val = [1 for i in range(n + 1)]
	dfs(1, 0, deg, dp, val)
	print(val[1] % p)


t = int(input())
while t > 0:
	n = int(input())
	a = [[] for i in range(n + 1)]
	vis = [0 for i in range(n + 1)]
	for i in range(n - 1):
		(p, q) = map(int, input().split())
		a[p].append(q)
		a[q].append(p)
	p = [0 for i in range(n + 1)]
	for i in a:
		i.sort()
	z = [1]
	cc = []
	b = [[] for i in range(n + 1)]
	while len(z) != 0:
		cc.append(z)
		for i in z:
			vis[i] = 1
		zz = []
		for i in z:
			for j in a[i]:
				if vis[j] == 0:
					b[i].append(j)
					zz.append(j)
		z = zz
	u = 10 ** 9 + 7
	p = [0 for i in range(n + 1)]
	q = [0 for i in range(n + 1)]
	for i in range(len(cc) - 1, -1, -1):
		for j in cc[i]:
			if len(b[j]) == 0:
				p[j] = 1
				q[j] = 0
			else:
				gg = []
				s = 0
				for k in b[j]:
					s = s + p[k]
					gg.append(p[k])
				s = 2 * s + 1
				p[j] = s
				s = 0
				ff = []
				for k in gg:
					s = s + k
					ff.append(s)
				s = 0
				for k in range(len(gg) - 1):
					s = s + 2 * gg[k] * (ff[-1] - ff[k])
				q[j] = s
	print((p[1] + sum(q)) % u)
	t = t - 1


import sys
sys.setrecursionlimit(int(1000000.0))
m = int(1000000000.0) + 7
t = int(input())
while t:
	t -= 1
	n = int(input())
	adja = [[] for i in range(n)]
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		u -= 1
		v -= 1
		adja[u].append(v)
		adja[v].append(u)

	def dfs(node, ances, mul):
		const = mul
		sm = const
		path = 0
		for v in adja[node]:
			if v == ances:
				continue
			(a, b) = dfs(v, node, 2 * (path + const) % m)
			sm = (sm + a) % m
			path = (path + 2 * b - 1) % m
		return (sm, path + 1)
	(res, p) = dfs(0, -1, 1)
	print(res % m)


import sys
sys.setrecursionlimit(10 ** 5 + 1)
m = 10 ** 9 + 7

def cal_sum(arr):
	cs = 0
	ts = 0
	for v in arr:
		ts = (ts + cs * v) % m
		cs = (cs + v) % m
	return 2 * ts % m

def bfs(u, tree, vis):
	vis[u] = True
	sbt_nums = []
	tsum = 0
	for v in tree[u]:
		if not vis[v]:
			(sbtsum, sbtnum) = bfs(v, tree, vis)
			tsum = (tsum + sbtsum) % m
			sbt_nums.append(sbtnum)
	tnum = (2 * sum(sbt_nums) + 1) % m
	tsum = (tsum + cal_sum(sbt_nums)) % m
	return (tsum, tnum)

def solve(tree, vis):
	root = 1
	(tsum, tnum) = bfs(root, tree, vis)
	return (tsum + tnum) % m
for t in range(int(input())):
	n = int(input())
	tree = dict()
	for i in range(1, n + 1):
		tree[i] = []
	for i in range(n - 1):
		(u, v) = tuple(map(int, input().strip().split()))
		tree[u].append(v)
		tree[v].append(u)
	vis = [False for i in range(n + 1)]
	ans = solve(tree, vis)
	print(ans)


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

def dfs(node, parent):
	down = []
	paths = []
	for child in graph[node]:
		if child != parent:
			(d, p) = dfs(child, node)
			down.append(d)
			paths.append(p)
	d_sum = sum(down) % MOD
	d_pairs = 0
	for d in down:
		d_pairs = (d_pairs + d * (d_sum - d)) % MOD
	valid_paths = (sum(paths) + d_sum + 1 + d_pairs) % MOD
	down_paths = (d_sum * 2 + 1) % MOD
	return (down_paths, valid_paths)

def solve():
	(_, paths) = dfs(1, 1)
	return paths
test_cases = int(input())
for test_case in range(test_cases):
	N = int(input())
	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())


import sys
sys.setrecursionlimit(10 ** 6)

def rec(x, y, z):
	if len(y[x]) == 1 and y[x][0] == z:
		return (1, 1)
	ans = 1
	ans1 = 1
	a = 0
	for i in y[x]:
		if i != z:
			(temp1, temp2) = rec(i, y, x)
			ans += temp1 + temp2
			ans -= temp2 ** 2
			ans1 += 2 * temp2
			a += temp2
	ans += a ** 2
	return (ans % 1000000007, ans1 % 1000000007)
for t in range(int(input())):
	n = int(input())
	a1 = [[] for i in range(n + 1)]
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		a1[u].append(v)
		a1[v].append(u)
	(ai, aj) = rec(1, a1, 0)
	print(ai % 1000000007)


import itertools
import sys
sys.setrecursionlimit(3 * 10 ** 5)
MODULUS = 10 ** 9 + 7

def number_of_valid_paths(tree, root, parent):
	subtrees = [number_of_valid_paths(tree, node, root) for node in tree[root] if node != parent]
	result = (sum((v + s for (v, s) in subtrees)) + 2 * sum((s * (a - s) for ((v, s), a) in zip(subtrees, itertools.accumulate((s for (_, s) in subtrees))))) + 1, 2 * sum((s for (_, s) in subtrees)) + 1)
	return (result[0] % MODULUS, result[1] % MODULUS)
for _ in range(int(input())):
	number_of_nodes = int(input())
	tree = [[] for _ in range(number_of_nodes)]
	for _ in range(number_of_nodes - 1):
		(u, v) = [int(x) - 1 for x in input().split()]
		tree[u].append(v)
		tree[v].append(u)
	print(number_of_valid_paths(tree, 0, None)[0])