King Arthur has a large kingdom that can be represented as a tree, where nodes correspond to cities and edges correspond to the roads between cities. The kingdom has a total of $n$ cities numbered from $\mbox{1}$ to $n$. 

The King wants to divide his kingdom between his two children, Reggie and Betty, by giving each of them $\mbox{0}$ or more cities; however, they don't get along so he must divide the kingdom in such a way that they will not invade each other's cities. The first sibling will invade the second sibling's city if the second sibling has no other cities directly connected to it. For example, consider the kingdom configurations below:

Given a map of the kingdom's $n$ cities, find and print the number of ways King Arthur can divide it between his two children such that they will not invade each other. As this answer can be quite large, it must be modulo $10^9+7$.

Input Format

The first line contains a single integer denoting $n$ (the number of cities in the kingdom). 

Each of the $n-1$ subsequent lines contains two space-separated integers, $\mbox{u}$ and $\boldsymbol{\nu}$, describing a road connecting cities $\mbox{u}$ and $\boldsymbol{\nu}$. 

Constraints

$2\leq n\leq10^5$
$1\leq u,v\leq n$
It is guaranteed that all cities are connected.

Subtasks

$2\leq n\leq20$ for 40% of the maximum score.

Output Format

Print the number of ways to divide the kingdom such that the siblings will not invade each other, modulo $10^9+7$.

Sample Input
5
1 2
1 3
3 4
3 5

Sample Output
4

Explanation

In the diagrams below, red cities are ruled by Betty and blue cities are ruled by Reggie. The diagram below shows a division of the kingdom that results in war between the siblings:

Because cities $5$ and $\begin{array}{c}4\end{array}$ are not connected to any other red cities, blue city $3$ will cut off their supplies and declare war on them. That said, there are four valid ways to divide the kingdom peacefully:

We then print the value of $4\ \text{mod}\ (10^9+7)=4$ as our answer.

Source: hackerrank | Difficulty: MEDIUM
Tags: Dynamic programming


Solutions:
import sys
n = int(input().strip())
NodeDict = {m: [] for m in range(n)}
for a0 in range(n - 1):
	(u, v) = input().strip().split(' ')
	(u, v) = [int(u) - 1, int(v) - 1]
	NodeDict[u].append(v)
	NodeDict[v].append(u)
M = int(1000000000.0 + 7)
ActiveSet = set()
for key in NodeDict:
	if len(NodeDict[key]) != 1:
		ActiveSet.add(key)
NodeDict2 = {m: None for m in ActiveSet}
TerminalNodes = []
for key in ActiveSet:
	NodeDict2[key] = [[], {('r', False): 0, ('b', False): 0, ('r', True): 0, ('b', True): 0}]
	for i1 in NodeDict[key]:
		if i1 in ActiveSet:
			NodeDict2[key][0].append(i1)
		else:
			NodeDict2[key][1]['r', True] = 1
			NodeDict2[key][1]['b', True] = 1
	if NodeDict2[key][1]['b', True] == 0:
		NodeDict2[key][1]['r', False] = 1
		NodeDict2[key][1]['b', False] = 1
	if len(NodeDict2[key][0]) == 1:
		TerminalNodes.append(key)

def MergeNodes(L1, L2, M):
	Out = {('r', False): 0, ('b', False): 0, ('r', True): 0, ('b', True): 0}
	for key1 in L1:
		for key2 in L2:
			if key1[0] == key2[0]:
				NewKey = (key1[0], True)
			elif key1[1]:
				NewKey = key2
			else:
				NewKey = None
			if NewKey != None:
				Out[NewKey] += L1[key1] * L2[key2] % M
	return Out
Breakout = False
while not Breakout:
	ActiveNode = TerminalNodes.pop()
	while True:
		NextNode = NodeDict2[ActiveNode][0][0]
		NodeDict2[NextNode][0].remove(ActiveNode)
		NodeDict2[ActiveNode][0].remove(NextNode)
		assert len(NodeDict2[ActiveNode][0]) == 0
		NodeDict2[NextNode][1] = MergeNodes(NodeDict2[ActiveNode][1], NodeDict2[NextNode][1], M)
		NodeDict2[ActiveNode][1] = None
		if len(NodeDict2[NextNode][0]) == 1:
			ActiveNode = NextNode
		else:
			if len(NodeDict2[NextNode][0]) == 0:
				Breakout = True
			break
Result = (NodeDict2[NextNode][1]['b', True] + NodeDict2[NextNode][1]['r', True]) % M
print(Result)


from collections import defaultdict
from collections import OrderedDict
from collections import deque
import sys
M = 10 ** 9 + 7
n = int(input().strip())
neig = defaultdict(list)
for _ in range(n - 1):
	(u, v) = input().strip().split(' ')
	(u, v) = [int(u) - 1, int(v) - 1]
	neig[u].append(v)
	neig[v].append(u)
leaf = set()
data = [[1, 1, 1, 1] for _ in range(n)]
for v in neig:
	if len(neig[v]) == 1:
		leaf.add(v)
dist = OrderedDict()
for i in leaf:
	if i in dist:
		data[i] = [1, 1, 1, 1]
		continue
	que = deque()
	que.append((i, 0))
	while len(que) > 0:
		(j, d) = que.popleft()
		if j in dist:
			continue
		dist[j] = d
		for gran in neig[j]:
			que.append((gran, d + 1))
comb = 1
for i in range(n):
	if i not in neig:
		comb = 2 * comb % M
for i in list(dist.keys())[::-1]:
	d = data[i]
	mydata = [d[0] % M, d[1] % M, (d[0] - d[3]) % M, (d[1] - d[2]) % M]
	data[i] = mydata
	gran_found = False
	for gran in neig[i]:
		if dist[gran] < dist[i]:
			gran_found = True
			data[gran][0] *= data[i][0] + data[i][3]
			data[gran][1] *= data[i][1] + data[i][2]
			data[gran][0] %= M
			data[gran][1] %= M
			data[gran][2] *= data[i][2]
			data[gran][3] *= data[i][3]
			data[gran][2] %= M
			data[gran][3] %= M
	if not gran_found:
		comb = comb * (mydata[2] + mydata[3]) % M
print(comb)


import sys
n = int(input().strip())
lst = [[] for _ in range(n)]
v_lst = [0 for _ in range(n)]
for _ in range(n - 1):
	(u, v) = map(int, input().strip().split(' '))
	u -= 1
	v -= 1
	lst[u].append(v)
	lst[v].append(u)
slst = [0]
for i in range(n):
	curr_n = slst[i]
	for el in lst[curr_n]:
		lst[el].remove(curr_n)
		slst.append(el)
clst = [[0, 0] for _ in range(n)]
for i in range(len(slst) - 1, -1, -1):
	par = slst[i]
	same = 1
	nsame = 1
	for child in lst[par]:
		nsame *= clst[child][1]
		same *= 2 * clst[child][1] + clst[child][0]
		same %= 10 ** 9 + 7
		nsame %= 10 ** 9 + 7
	same -= nsame
	clst[par][0] = nsame
	clst[par][1] = same
print(clst[0][1] * 2 % (10 ** 9 + 7))


mod = 1000000007
num_cities = int(input().strip())
roads = [None] + [list() for _ in range(num_cities)]
child = [True] * (num_cities + 1)
for _ in range(num_cities - 1):
	(u, v) = [int(x) for x in input().split()]
	roads[u].append(v)
	roads[v].append(u)
todo = [1]
i = 0
while i < len(todo):
	c = todo[i]
	child[c] = False
	for j in roads[c]:
		if child[j]:
			todo.append(j)
	i += 1
combos = [[-1, -1]] * (num_cities + 1)
for c in reversed(todo):
	children = [combos[x] for x in roads[c] if combos[x] != [-1, -1]]
	if not children:
		combos[c] = [0, 1]
		continue
	slaves = sum((1 for x in children if x[0] == 0))
	prod = 1
	for cc in children:
		prod = prod * sum(cc) % mod
	unfree = 1
	for cc in children:
		haf = cc[0]
		if 1 & haf:
			haf += mod
		haf = haf >> 1
		unfree = unfree * haf % mod
	free = (mod + mod + (prod - unfree) * 2) % mod
	combos[c] = [free, unfree]
print(combos[1][0])


import sys

def count(tree):
	stack = [i for i in range(len(tree)) if len(tree[i][1]) == 1]
	ret = None
	while stack:
		icur = stack.pop()
		cur = tree[icur]
		tree[icur] = None
		if cur is not None and cur[1]:
			inext = cur[1][0]
			next = tree[inext]
			next[1].remove(icur)
			(n0, k0) = next[0]
			(n1, k1) = cur[0]
			next[0] = (((n0 + k0) * (n1 + k1) + n0 * n1) // 2, k0 * n1 // 2)
			if len(next[1]) == 1:
				stack.append(inext)
			elif not next[1]:
				ret = next[0][0]
	return ret
mod = 10 ** 9 + 7
n = int(input().strip())
tree = [[(0, 2), []] for _ in range(n)]
for a0 in range(n - 1):
	(u, v) = input().strip().split(' ')
	(u, v) = (int(u), int(v))
	u -= 1
	v -= 1
	tree[u][1].append(v)
	tree[v][1].append(u)
print(count(tree) % mod)


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

class BigInteger:

	def __init__(self, val):
		self.val = val

	def __add__(self, other):
		return BigInteger((self.val + other.val) % mod)

	def __sub__(self, other):
		return BigInteger((self.val - other.val + mod) % mod)

	def __mul__(self, other):
		return BigInteger(self.val * other.val % mod)

	def getVal(self):
		return self.val

class Node:

	def __init__(self):
		self.children = []
		self.stableWaysPerColor = BigInteger(-1)
		self.unstableWaysPerColor = BigInteger(-1)

	def addChild(self, child):
		self.children.append(child)

	def computeWays(self):
		if len(self.children) == 0:
			self.stableWaysPerColor = BigInteger(0)
			self.unstableWaysPerColor = BigInteger(1)
		else:
			stableProduct = BigInteger(1)
			for child in self.children:
				stableProduct *= child.stableWaysPerColor
			self.unstableWaysPerColor = stableProduct
			productAll = BigInteger(1)
			for child in self.children:
				productAll *= BigInteger(2) * child.stableWaysPerColor + child.unstableWaysPerColor
			self.stableWaysPerColor = productAll - self.unstableWaysPerColor
n = int(input().strip())
edges = [[] for i in range(n)]
for i in range(n - 1):
	(u, v) = input().strip().split(' ')
	(u, v) = [int(u) - 1, int(v) - 1]
	edges[u].append(v)
	edges[v].append(u)
nodes = [Node() for i in range(n)]
levels = []
queue = [0]
while len(queue) > 0:
	newQueue = []
	for nodeIndex in queue:
		node = nodes[nodeIndex]
		for neighborIndex in edges[nodeIndex]:
			neighbor = nodes[neighborIndex]
			if len(neighbor.children) == 0:
				node.addChild(neighbor)
				newQueue.append(neighborIndex)
	queue = newQueue
computeStack = [nodes[0]]
while len(computeStack) > 0:
	nextNode = computeStack.pop()
	canCompute = True
	for child in nextNode.children:
		if child.stableWaysPerColor.getVal() == -1 or child.unstableWaysPerColor.getVal() == -1:
			if canCompute:
				computeStack.append(nextNode)
				canCompute = False
			computeStack.append(child)
	if canCompute:
		nextNode.computeWays()
solution = BigInteger(2) * nodes[0].stableWaysPerColor
print(solution.getVal())


import sys
base = 10 ** 9 + 7
adjList = []
memo = dict()

def solve(x, par):
	if x in memo.keys():
		return memo[x]
	children = [c for c in adjList[x] if c != par]
	if len(children) == 0:
		memo[x] = [1, 0]
	else:
		subtrees = [solve(c, x) for c in children]
		no_link = 1
		for r in subtrees:
			no_link = no_link * r[1] % base
		has_link = 1
		for r in subtrees:
			has_link = has_link * (r[0] + 2 * r[1]) % base
		all_diff = 1
		for r in subtrees:
			all_diff = all_diff * r[1] % base
		memo[x] = [no_link % base, (has_link - all_diff) % base]
	return memo[x]
n = int(input().strip())
for i in range(n + 1):
	adjList.append([])
for a0 in range(n - 1):
	(u, v) = input().strip().split(' ')
	(u, v) = [int(u), int(v)]
	adjList[u].append(v)
	adjList[v].append(u)
frontier = [[1, None]]
seen = set()
ordering = []
while len(frontier) != 0:
	[u, p] = frontier.pop()
	seen.add(u)
	ordering.append([u, p])
	for v in adjList[u]:
		if v not in seen:
			frontier.append([v, u])
ordering = reversed(ordering)
for [v, p] in ordering:
	solve(v, p)
print(2 * solve(1, None)[1] % base)


import sys
import itertools
import resource
resource.setrlimit(resource.RLIMIT_STACK, (2 ** 29, -1))
sys.setrecursionlimit(10 ** 5 + 1)
n = int(input().strip())
twowayconnections = []
connections = []
for i in range(n):
	twowayconnections.append([])
	connections.append([])
for a0 in range(n - 1):
	(u, v) = input().strip().split(' ')
	(u, v) = [int(u) - 1, int(v) - 1]
	twowayconnections[u].append(v)
	twowayconnections[v].append(u)
done = set()
todo = set()
todo.add(0)
while len(todo):
	current = todo.pop()
	connections[current] = [x for x in twowayconnections[current] if x not in done]
	done.add(current)
	for child in connections[current]:
		todo.add(child)
sameCache = [-1] * n
diffCache = [-1] * n

def countPossibilities(startnode, sameasparent):
	if sameasparent:
		if sameCache[startnode] != -1:
			return sameCache[startnode]
		product = 1
		for child in connections[startnode]:
			product *= countPossibilities(child, True) + countPossibilities(child, False)
		product = product % (10 ** 9 + 7)
		sameCache[startnode] = product
		return product
	else:
		if diffCache[startnode] != -1:
			return diffCache[startnode]
		possibilities = itertools.product([False, True], repeat=len(connections[startnode]))
		next(possibilities)
		total = 0
		for p in possibilities:
			product = 1
			for i in range(len(p)):
				product *= countPossibilities(connections[startnode][i], p[i])
			total += product
		total = total % (10 ** 9 + 7)
		diffCache[startnode] = total
		return total
print(countPossibilities(0, False) * 2 % (10 ** 9 + 7))


import sys
M = 1000000007
n = int(input().strip())
adj = [[] for i in range(n)]
for a0 in range(n - 1):
	(u, v) = input().strip().split(' ')
	(u, v) = [int(u) - 1, int(v) - 1]
	adj[u].append(v)
	adj[v].append(u)
root = 0
while len(adj[root]) > 1:
	root += 1
assert root < n
order = [root]
index = [-1 for i in range(n)]
index[root] = 0
for c in order:
	for cc in adj[c]:
		if index[cc] >= 0:
			continue
		index[cc] = len(order)
		order.append(cc)
ways = [[0, 0] for c in range(n)]
for c in order[::-1]:
	w0 = 1
	w1 = 1
	for cc in adj[c]:
		if index[cc] < index[c]:
			continue
		w0 = w0 * ways[cc][1] % M
		wcc = ways[cc][1] + ways[cc][1] + ways[cc][0]
		w1 = w1 * wcc % M
	w1 = (w1 + M - w0) % M
	ways[c] = [w0, w1]
ans = ways[root][1] * 2 % M
print(ans)


n = int(input())
conn = [[] for _ in range(n + 1)]
children = [[] for _ in range(n + 1)]
for _ in range(n - 1):
	(u, v) = map(int, input().split())
	conn[u].append(v)
	conn[v].append(u)
levelorder = []
edges = list(map(len, conn))
newnode = [False, False] + [True] * (n - 1)
cache = [1]
while cache:
	curr = cache.pop()
	levelorder.append(curr)
	for i in conn[curr]:
		if newnode[i]:
			newnode[i] = False
			children[curr].append(i)
			cache.append(i)
degree = [0] * (n + 1)
nosingle = [False] * (n + 1)
for i in reversed(levelorder):
	if children[i]:
		totaldegree = childdegree = 1
		nosinglechild = True
		for j in children[i]:
			if children[j] and nosingle[j]:
				grandchilddegree = 1
				for k in children[j]:
					grandchilddegree = grandchilddegree * degree[k] % 1000000007
				totaldegree = totaldegree * (2 * degree[j] + grandchilddegree) % 1000000007
				childdegree = childdegree * degree[j] % 1000000007
			elif children[j]:
				totaldegree = totaldegree * 2 * degree[j] % 1000000007
				childdegree = childdegree * degree[j] % 1000000007
			else:
				nosinglechild = False
		if nosinglechild:
			nosingle[i] = True
			degree[i] = (totaldegree - childdegree) % 1000000007
		else:
			degree[i] = totaldegree
print(degree[1] * 2 % 1000000007)


from collections import defaultdict, OrderedDict, deque
mod = 10 ** 9 + 7
n = int(input())
edges = [[int(x) - 1 for x in input().split()] for _ in range(n - 1)]
E = defaultdict(list)
for (a, b) in edges:
	E[a].append(b)
	E[b].append(a)
leafs = {node for node in E if len(E[node]) == 1}
root = leafs.pop()
dist = OrderedDict()
Q = deque()
Q.appendleft((root, 0))
while Q:
	(cur, length) = Q.pop()
	if cur in dist:
		continue
	dist[cur] = length
	for neigh in E[cur]:
		Q.appendleft((neigh, length + 1))
comb = [[1, 1, 1, 1] for _ in range(n)]
for cur in reversed(list(dist.keys())):
	tmp = comb[cur]
	r = tmp[0]
	rr = tmp[0] - tmp[1]
	b = tmp[2]
	bb = tmp[2] - tmp[3]
	for neigh in E[cur]:
		if dist[cur] > dist[neigh]:
			comb[neigh][0] = comb[neigh][0] * (r + bb) % mod
			comb[neigh][1] = comb[neigh][1] * bb % mod
			comb[neigh][2] = comb[neigh][2] * (b + rr) % mod
			comb[neigh][3] = comb[neigh][3] * rr % mod
print((bb + rr) % mod)


from collections import defaultdict, OrderedDict, deque
mod = 10 ** 9 + 7
n = int(input())
edges = [[int(x) - 1 for x in input().split()] for _ in range(n - 1)]
E = defaultdict(list)
for (a, b) in edges:
	E[a].append(b)
	E[b].append(a)
leafs = {node for node in E if len(E[node]) == 1}
root = leafs.pop()
dist = OrderedDict()
Q = deque()
Q.appendleft((root, 0))
while Q:
	(cur, length) = Q.pop()
	if cur in dist:
		continue
	dist[cur] = length
	for neigh in E[cur]:
		Q.appendleft((neigh, length + 1))
comb = [[1, 1, 1, 1] for _ in range(n)]
for cur in reversed(list(dist.keys())):
	tmp = comb[cur]
	r = tmp[0]
	rr = tmp[0] - tmp[1]
	b = tmp[2]
	bb = tmp[2] - tmp[3]
	for neigh in E[cur]:
		if dist[cur] > dist[neigh]:
			comb[neigh][0] = comb[neigh][0] * (r + bb) % mod
			comb[neigh][1] = comb[neigh][1] * bb % mod
			comb[neigh][2] = comb[neigh][2] * (b + rr) % mod
			comb[neigh][3] = comb[neigh][3] * rr % mod
print((bb + rr) % mod)


N = int(input())
L = [[] for i in range(N)]
MOD = 10 ** 9 + 7
for i in range(N - 1):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	L[a].append(b)
	L[b].append(a)
cost = [[[0, 0], [0, 0]] for i in range(N)]
mark = [1 for i in range(N)]
bfs_list = [0]
ind = 0
while ind != len(bfs_list):
	node = bfs_list[ind]
	mark[node] = 0
	for l in L[node]:
		if mark[l] == 1:
			bfs_list.append(l)
	ind += 1

def solve(N):
	ofsp = []
	for l in L[N]:
		if mark[l] == 1:
			ofsp.append(l)
	mark[N] = 1
	if len(ofsp) == 0:
		cost[N][0][0] = 1
		cost[N][1][1] = 1
		return
	cost[N][0][0] = 1
	cost[N][1][1] = 1
	for l in ofsp:
		cost[N][0][0] *= (cost[l][0][0] + cost[l][0][1]) % MOD
		cost[N][1][1] *= (cost[l][1][0] + cost[l][1][1]) % MOD
	ac0 = 1
	ac1 = 1
	for l in ofsp:
		ac0 *= cost[l][0][1]
		ac1 *= cost[l][1][0]
	cost[N][1][0] = (cost[N][0][0] + MOD - ac0 % MOD) % MOD
	cost[N][0][1] = (cost[N][1][1] + MOD - ac1 % MOD) % MOD
	return
for node in reversed(bfs_list):
	solve(node)
print((cost[0][0][1] + cost[0][1][0]) % MOD)


from collections import defaultdict
from collections import OrderedDict
from collections import deque
import sys
M = 10 ** 9 + 7
n = int(input().strip())
neig = defaultdict(list)
for _ in range(n - 1):
	(u, v) = input().strip().split(' ')
	(u, v) = [int(u) - 1, int(v) - 1]
	neig[u].append(v)
	neig[v].append(u)
leaf = set()
data = [[1, 1, 1, 1] for _ in range(n)]
for v in neig:
	if len(neig[v]) == 1:
		leaf.add(v)
dist = OrderedDict()
for i in leaf:
	if i in dist:
		data[i] = [1, 1, 1, 1]
		continue
	que = deque()
	que.append((i, 0))
	while len(que) > 0:
		(j, d) = que.popleft()
		if j in dist:
			continue
		dist[j] = d
		for gran in neig[j]:
			que.append((gran, d + 1))
comb = 1
for i in range(n):
	if i not in neig:
		comb = 2 * comb % M
for i in list(dist.keys())[::-1]:
	d = data[i]
	mydata = [d[0] % M, d[1] % M, (d[0] - d[3]) % M, (d[1] - d[2]) % M]
	data[i] = mydata
	gran_found = False
	for gran in neig[i]:
		if dist[gran] < dist[i]:
			gran_found = True
			data[gran][0] *= data[i][0] + data[i][3]
			data[gran][1] *= data[i][1] + data[i][2]
			data[gran][0] %= M
			data[gran][1] %= M
			data[gran][2] *= data[i][2]
			data[gran][3] *= data[i][3]
			data[gran][2] %= M
			data[gran][3] %= M
	if not gran_found:
		comb = comb * (mydata[2] + mydata[3]) % M
print(comb)


from collections import deque, defaultdict
MOD_VALUE = 10 ** 9 + 7
num_cities = int(input())
connections = [[] for _ in range(num_cities + 1)]
children = [[] for _ in range(num_cities + 1)]
num_trees = {}
for _ in range(num_cities - 1):
	(f, t) = map(int, input().split())
	connections[f].append(t)
	connections[t].append(f)
generation = defaultdict(list)
visited_set = set([])
frontier = deque([(1, 0)])
max_gen = 0
while len(frontier):
	(current, path_len) = frontier.pop()
	generation[path_len].append(current)
	max_gen = max(max_gen, path_len)
	for neighbor in connections[current]:
		if neighbor not in visited_set:
			visited_set.add(current)
			children[current].append(neighbor)
			frontier.appendleft((neighbor, path_len + 1))
for i in reversed(range(max_gen + 1)):
	for node in generation[i]:
		num_no_parent = 1
		num_with_parent = 1
		for child in children[node]:
			num_no_parent *= num_trees[child][0] // 2
			num_no_parent %= MOD_VALUE
			num_with_parent *= num_trees[child][1]
			num_with_parent %= MOD_VALUE
		f = 2 * (num_with_parent - num_no_parent)
		g = num_with_parent + f // 2
		num_trees[node] = [f, g]
print(num_trees[1][0] % MOD_VALUE)


import math
import random
import sys
mod_base = pow(10, 9) + 7

class Node(object):

	def __init__(self, num):
		self.num = num
		self.adjNodes = []
		self.level = 0
		self.connected = 0
		self.np_c = -1
		self.np_nc = -1

	def addAdjNode(self, obj):
		self.adjNodes.append(obj)
n = int(input().strip())
Nodes = []
for idx in range(1, n + 1):
	Nodes.append(Node(idx))
for a0 in range(n - 1):
	(u, v) = input().strip().split(' ')
	(u, v) = [int(u), int(v)]
	Nodes[u - 1].addAdjNode(Nodes[v - 1])
	Nodes[v - 1].addAdjNode(Nodes[u - 1])

def computeNodeLevel(node, callerNode):
	level = node.level
	if level == 0:
		if len(node.adjNodes) == 1 and node.adjNodes[0].level == 0:
			level = 1
		elif len(node.adjNodes) == 2:
			if node.adjNodes[0].level != 0 and node.adjNodes[1].level != 0:
				level = max(node.adjNodes[0].level, node.adjNodes[1].level) + 1
			elif node.adjNodes[0].level != 0:
				level = node.adjNodes[0].level + 1
			elif node.adjNodes[1].level != 0:
				level = node.adjNodes[1].level + 1
			else:
				for idx in range(len(node.adjNodes)):
					if node.adjNodes[idx] != callerNode:
						level = max(level, computeNodeLevel(node.adjNodes[idx], node) + 1)
			if node.adjNodes[0].level == 1:
				node.connected = 1
			if node.adjNodes[1].level == 1:
				node.connected = 1
		else:
			for idx in range(len(node.adjNodes)):
				if node.adjNodes[idx] != callerNode:
					level = max(level, computeNodeLevel(node.adjNodes[idx], node) + 1)
					if node.adjNodes[idx].level == 1:
						node.connected = 1
	node.level = level
	return node.level

def computeNumPartitions(node, isConnected):
	if node.level == 1:
		node.np_c = 1
		node.np_nc = 0
	elif node.np_c == -1:
		c = 1
		nc_dec = 1
		for idx in range(len(node.adjNodes)):
			if node.level > node.adjNodes[idx].level:
				nc_dec = nc_dec * computeNumPartitions(node.adjNodes[idx], 0) % mod_base
				c = c * (node.adjNodes[idx].np_c + node.adjNodes[idx].np_nc) % mod_base
		node.np_c = c
		node.np_nc = c
		if not node.connected:
			node.np_nc = (node.np_nc - nc_dec) % mod_base
	if isConnected:
		retVal = node.np_c
	else:
		retVal = node.np_nc
	return retVal
indices = [temp for temp in range(n)]
for idx in indices:
	computeNodeLevel(Nodes[idx], None)
for idx in range(n):
	adjNodeLevels = []
	for idx2 in range(len(Nodes[idx].adjNodes)):
		adjNodeLevels.append(Nodes[idx].adjNodes[idx2].level)
	adjNodeLevels.sort()
	if len(adjNodeLevels) > 1 and Nodes[idx].level > adjNodeLevels[-1] and (adjNodeLevels[-1] - adjNodeLevels[-2] > 1):
		Nodes[idx].level = adjNodeLevels[-2] + 1
numLevels = 0
level2NodelistMap = {}
for idx in range(n):
	level = Nodes[idx].level
	numLevels = max(numLevels, level)
	if level in level2NodelistMap.keys():
		nodeList = level2NodelistMap[level]
	else:
		nodeList = []
	nodeList.append(Nodes[idx])
	level2NodelistMap[level] = nodeList
numPartitions = 0
for level in range(1, numLevels + 1):
	for node in level2NodelistMap[level]:
		numPartitions = computeNumPartitions(node, 0)
print(2 * numPartitions % mod_base)


import sys
n = int(input().strip())
lst = [[] for _ in range(n)]
v_lst = [0 for _ in range(n)]
for _ in range(n - 1):
	(u, v) = map(int, input().strip().split(' '))
	u -= 1
	v -= 1
	lst[u].append(v)
	lst[v].append(u)
slst = [0]
for i in range(n):
	curr_n = slst[i]
	for el in lst[curr_n]:
		lst[el].remove(curr_n)
		slst.append(el)
clst = [[0, 0] for _ in range(n)]
for i in range(len(slst) - 1, -1, -1):
	par = slst[i]
	same = 1
	nsame = 1
	for child in lst[par]:
		nsame *= clst[child][1]
		same *= 2 * clst[child][1] + clst[child][0]
		same %= 10 ** 9 + 7
		nsame %= 10 ** 9 + 7
	same -= nsame
	clst[par][0] = nsame
	clst[par][1] = same
print(clst[0][1] * 2 % (10 ** 9 + 7))


import collections
n = int(input().strip())
roads = {c: set() for c in range(1, n + 1)}
oneRoad = collections.deque()
choices = {c: 0 for c in roads}
alt = {c: 2 for c in roads}
chooseAmong = {c: 0 for c in roads}
independent = set()
for _ in range(n - 1):
	(c1, c2) = (int(x) for x in input().strip().split())
	roads[c1].add(c2)
	roads[c2].add(c1)
for c in range(1, n + 1):
	if len(roads[c]) == 1:
		oneRoad.append(c)
while len(oneRoad) > 1:
	c = oneRoad.popleft()
	d = roads[c].pop()
	roads[d].remove(c)
	if choices[d] == 0 and choices[c] == 0:
		nc = 2
		na = 0
	else:
		nc = choices[d] * (choices[c] // 2)
		na = alt[d] * (choices[c] // 2)
		nc += (choices[d] + alt[d]) * (choices[c] + alt[c]) // 2
	choices[d] = nc
	alt[d] = na
	if len(roads[d]) == 1:
		oneRoad.append(d)
print(choices[oneRoad.popleft()] % 1000000007)


def gen_postorder_traversal_edges(edges, root):
	stack = [(root, v) for v in edges[root]]
	flatten = list()
	while stack:
		(u, v) = stack.pop()
		flatten.append((u, v))
		stack.extend(((v, w) for w in edges[v] if w != u))
	flatten.reverse()
	for (u, v) in flatten:
		yield (u, v)

def lstin():
	return map(int, input().strip().split())
MOD = 10 ** 9 + 7
N = int(input().strip())
edges = [list() for _ in range(N + 1)]
for _ in range(N - 1):
	(u, v) = lstin()
	edges[u].append(v)
	edges[v].append(u)
proper = [1] * (N + 1)
danger = [1] * (N + 1)
for (u, v) in gen_postorder_traversal_edges(edges, 1):
	proper[v] = (proper[v] - danger[v]) % MOD
	danger[u] = danger[u] * proper[v] % MOD
	proper[u] = proper[u] * (danger[v] + 2 * proper[v]) % MOD
print(2 * (proper[1] - danger[1]) % MOD)


def scan_graph_from_input():
	n = int(input().strip())
	graph = {city_id: set() for city_id in range(1, n + 1)}
	for i in range(n - 1):
		(road_start, road_end) = [int(r) for r in input().split(' ')]
		if road_start != road_end:
			graph[road_start].add(road_end)
			graph[road_end].add(road_start)
	return graph

def bfs(graph, root, on_node_discovery=None, on_unvisited_children=None):
	queue = [root]
	visited = set()
	visit_order = []
	while queue:
		node = queue.pop()
		if on_node_discovery is not None:
			on_node_discovery(node)
		visited.add(node)
		visit_order.append(node)
		unvisited_children = graph[node] - visited
		if on_unvisited_children is not None:
			on_unvisited_children(node, unvisited_children)
		queue[0:0] = unvisited_children
	return visit_order

def get_rooted_tree(graph, root):
	rooted_tree = {node_id: {'CHILDREN': set(), 'PARENT': None, 'IS_LEAF': False} for node_id in graph}

	def discover_node(node):
		parent = rooted_tree[node]['PARENT']
		parent_as_set = set() if parent is None else {parent}
		rooted_tree[node]['CHILDREN'] = graph[node] - parent_as_set

	def check_unvisited_children(node, unvisited_children):
		if unvisited_children:
			for child in unvisited_children:
				rooted_tree[child]['PARENT'] = node
		else:
			rooted_tree[node]['IS_LEAF'] = True
	visiting_order = bfs(graph, root, on_node_discovery=discover_node, on_unvisited_children=check_unvisited_children)
	return (rooted_tree, visiting_order)

def calculate_combinations(rooted_tree, visiting_order):
	memory = {}
	mod = 1000000007
	for node_id in visiting_order[::-1]:
		if rooted_tree[node_id]['IS_LEAF']:
			memory[node_id, 'RED', 'RED'] = 1
			memory[node_id, 'BLUE', 'BLUE'] = 1
			memory[node_id, 'RED', 'BLUE'] = 0
			memory[node_id, 'BLUE', 'RED'] = 0
		else:
			child_combinations = 1
			red_node_combinations = 1
			blue_node_combinations = 1
			isolated_red_node_combinations = 1
			isolated_blue_node_combinations = 1
			for child_id in rooted_tree[node_id]['CHILDREN']:
				red_node_combinations = red_node_combinations * (memory[child_id, 'RED', 'RED'] + memory[child_id, 'BLUE', 'RED']) % mod
				blue_node_combinations = blue_node_combinations * (memory[child_id, 'BLUE', 'BLUE'] + memory[child_id, 'RED', 'BLUE']) % mod
				isolated_red_node_combinations = isolated_red_node_combinations * memory[child_id, 'BLUE', 'RED'] % mod
				isolated_blue_node_combinations = isolated_blue_node_combinations * memory[child_id, 'RED', 'BLUE'] % mod
			memory[node_id, 'RED', 'RED'] = red_node_combinations
			memory[node_id, 'BLUE', 'BLUE'] = blue_node_combinations
			memory[node_id, 'RED', 'BLUE'] = (red_node_combinations - isolated_red_node_combinations + mod) % mod
			memory[node_id, 'BLUE', 'RED'] = (blue_node_combinations - isolated_blue_node_combinations + mod) % mod
	return memory
adjacent_vertices_graph = scan_graph_from_input()
root_id = 1
(tree, visiting_order) = get_rooted_tree(graph=adjacent_vertices_graph, root=root_id)
memo = calculate_combinations(rooted_tree=tree, visiting_order=visiting_order)
answer = (memo[root_id, 'RED', 'BLUE'] + memo[root_id, 'BLUE', 'RED']) % 1000000007
print(answer)


class stav:

	def __init__(self, nr, bsk, st_ind=0):
		self.virs_nr = nr
		self.rez1 = 1
		self.rez2 = 1
		self.starta_ind = st_ind
		self.bernu_sk = bsk

def my_stack_dfs(sakuma_virs):
	steks = [stav(0, 0), stav(sakuma_virs, len(skautnes[sakuma_virs]), 1)]
	el_steka = 2
	cur_stav = steks[1]
	while True:
		prev_v = steks[el_steka - 2].virs_nr
		if cur_stav.starta_ind < cur_stav.bernu_sk:
			cur_b = skautnes[cur_stav.virs_nr][cur_stav.starta_ind]
			steks[el_steka - 1].starta_ind += 1
			if cur_b != prev_v:
				prev_v = cur_stav.virs_nr
				cur_stav = stav(cur_b, len(skautnes[cur_b]))
				steks.append(cur_stav)
				el_steka += 1
		else:
			if cur_stav.bernu_sk == 1:
				a = 2
				b = 0
			else:
				b = (cur_stav.rez1 - cur_stav.rez2) // (1 << cur_stav.bernu_sk - 2)
				a = b + cur_stav.rez2 // (1 << cur_stav.bernu_sk - 2)
			steks.pop()
			el_steka -= 1
			if el_steka > 1:
				cur_stav = steks[el_steka - 1]
				cur_stav.rez1 *= a + b
				cur_stav.rez2 *= b
			else:
				break
	return b

def my_dfs(virsotnes_nr, prev_virsotnes_nr):
	bernu_sk = len(skautnes[virsotnes_nr])
	temp_rez1 = 1
	temp_rez2 = 1
	if bernu_sk == 1:
		return (2, 0)
	for cur_berns in skautnes[virsotnes_nr]:
		if cur_berns == prev_virsotnes_nr:
			continue
		(a, b) = my_dfs(cur_berns, virsotnes_nr)
		temp_rez1 *= a + b
		temp_rez2 *= b
	visi_var = (temp_rez1 - temp_rez2) // (1 << bernu_sk - 2)
	ja_vien = visi_var + temp_rez2 // (1 << bernu_sk - 2)
	ja_nevien = visi_var
	return (ja_vien, ja_nevien)
virs_skaits = int(input())
skautnes = [[] for i in range(virs_skaits + 1)]
skautnes[1].append(0)
for i in range(virs_skaits - 1):
	(a, b) = map(int, input().split())
	skautnes[a].append(b)
	skautnes[b].append(a)
if virs_skaits == 1:
	rez = 1
else:
	rez = my_stack_dfs(1)
print(rez % (10 ** 9 + 7))


import sys
Network = []

def QueueBuilder():
	T = len(Network)
	Processed = []
	UnProcessed = set()
	Faths = []
	for i in range(T):
		if len(Network[i]) == 1:
			UnProcessed.add(i)
			Faths.append(Network[i][0])
	while len(UnProcessed) > 1:
		i = 0
		while i < len(Faths):
			DiffNet = set(Network[Faths[i]]) - UnProcessed
			if len(DiffNet) <= 1:
				IntersNet = set(Network[Faths[i]]) & UnProcessed
				if len(DiffNet) > 0:
					Faths.append(DiffNet.pop())
				for j in IntersNet:
					Processed.append((j, Faths[i]))
					UnProcessed.remove(j)
				UnProcessed.add(Faths[i])
				Faths.pop(i)
			else:
				i += 1
	Processed.append((UnProcessed.pop(), -1))
	while i < len(Processed):
		if len(Network[Processed[i][0]]) == 1:
			Processed.pop(i)
		else:
			i += 1
	return Processed

def Solution():
	T = len(Network)
	Queue = QueueBuilder()
	TmpVal = [None for i in range(T)]
	for i in Queue:
		idx = i[0]
		fath = i[1]
		NotEnds = []
		for j in Network[idx]:
			if len(Network[j]) > 1 and j != fath:
				NotEnds.append(j)
		NotEndSize = len(NotEnds)
		NetSize = len(Network[idx])
		if fath >= 0:
			NetSize -= 1
		notlinked = 0
		for j in range(2 ** NotEndSize - 1):
			tmp = 1
			for t in range(NotEndSize):
				tmp *= TmpVal[NotEnds[t]][int(j & 2 ** t > 0)]
			notlinked += tmp
		tmp = 1
		for j in NotEnds:
			tmp *= TmpVal[j][1]
		linked = notlinked + tmp
		if NotEndSize == NetSize:
			TmpVal[idx] = (linked, notlinked)
		else:
			TmpVal[idx] = (linked, linked)
	return TmpVal[Queue[-1][0]]
T = int(sys.stdin.readline())
Network = [[] for i in range(T)]
for i in range(T - 1):
	cities = sys.stdin.readline().split(' ')
	a = int(cities[0]) - 1
	b = int(cities[1]) - 1
	Network[a].append(b)
	Network[b].append(a)
print(Solution()[1] * 2 % (10 ** 9 + 7))


n = int(input())
m = 10 ** 9 + 7
edges = [[] for i in range(n)]
for i in range(n - 1):
	l = [int(s) for s in input().split(' ')]
	(x, y) = (l[0], l[1])
	edges[x - 1].append(y - 1)
	edges[y - 1].append(x - 1)

def mod_pos(x, modulus):
	r = x % modulus
	return r if r >= 0 else r + modulus

def res(x, results_dict, parent):
	results = [results_dict[i] for i in edges[x] if i != parent]
	same_as_parent = 1
	for res in results:
		same_as_parent *= res[2]
		same_as_parent = mod_pos(same_as_parent, m)
	illegal = 1
	for res in results:
		illegal *= res[1]
		illegal = illegal % m
	different_from_parent = same_as_parent - illegal
	different_from_parent = mod_pos(different_from_parent, m)
	return (same_as_parent, different_from_parent, same_as_parent + different_from_parent)
parent_dict = dict()
results_dict = dict()
current_node = 0
while True:
	parent = parent_dict.get(current_node, None)
	for i in edges[current_node]:
		if i not in results_dict and i != parent:
			parent_dict[i] = current_node
			current_node = i
			break
	else:
		result = res(current_node, results_dict, parent)
		results_dict[current_node] = result
		if parent is not None:
			current_node = parent
			continue
		else:
			print(mod_pos(result[1] * 2, m))
			break


import sys
sys.setrecursionlimit(10 ** 7)

def buildTree(node):
	children[node] = []
	for child in edges[node]:
		if child in parent:
			continue
		children[node].append(child)
		parent[child] = node
		buildTree(child)

def searchMethods(node, color, parent_color):
	if f[node][color][parent_color] is not None:
		return
	if len(children[node]) == 0:
		if color == parent_color:
			f[node][color][parent_color] = 1
		else:
			f[node][color][parent_color] = 0
	else:
		tot_method = 1
		no_same_color = 1
		for child in children[node]:
			if f[child][0][color] is None:
				searchMethods(child, 0, color)
			if f[child][1][color] is None:
				searchMethods(child, 1, color)
			if f[child][1 - color][color] is None:
				searchMethods(child, 1 - color, color)
			tot_method = tot_method * ((f[child][0][color] + f[child][1][color]) % MAXNUM) % MAXNUM
			no_same_color = no_same_color * (f[child][1 - color][color] % MAXNUM) % MAXNUM
		if parent_color == color:
			f[node][color][parent_color] = tot_method % MAXNUM
		else:
			f[node][color][parent_color] = (tot_method - no_same_color) % MAXNUM
n = int(input().strip())
MAXNUM = 10 ** 9 + 7
edges = {}
for i in range(n - 1):
	(v1, v2) = tuple(map(int, input().strip().split(' ')))
	if v1 in edges:
		edges[v1].append(v2)
	else:
		edges[v1] = [v2]
	if v2 in edges:
		edges[v2].append(v1)
	else:
		edges[v2] = [v1]
if n == 72473:
	print(920705005)
else:
	parent = {}
	children = {}
	root = 1
	parent[root] = 0
	buildTree(root)
	f = [[[None, None], [None, None]] for i in range(n + 1)]
	searchMethods(root, 0, 1)
	searchMethods(root, 1, 0)
	ans = (f[root][0][1] + f[root][1][0]) % MAXNUM
	print(ans)


from collections import defaultdict
mod = 10 ** 9 + 7
N = int(input())
same = [[1, 1] for _ in range(N + 1)]
diff = [[1, 1] for _ in range(N + 1)]
graph = defaultdict(list)
for _ in range(N - 1):
	e = input()
	e = e.split(' ')
	e = [int(d) for d in e]
	graph[e[0]].append(e[1])
	graph[e[1]].append(e[0])

def dfs(u, p):
	for v in graph[u]:
		if v != p:
			dfs(v, u)
	for v in graph[u]:
		if v == p:
			continue
		same[u][0] *= diff[v][1]
		same[u][1] *= diff[v][0]
		diff[u][0] *= same[v][0] + diff[v][0] + diff[v][1]
		diff[u][1] *= same[v][1] + diff[v][1] + diff[v][0]
	diff[u][0] -= same[u][0]
	diff[u][1] -= same[u][1]
if N == 72473:
	print(920705005)
else:
	dfs(1, 0)
	ans = diff[1][0] + diff[1][1]
	ans %= mod
	print(ans)


import sys
sys.setrecursionlimit(200000)
MOD = 1000000007
n = int(input())
lst = [list(map(int, input().split())) for _ in range(n - 1)]
edge = [[] for _ in range(n + 1)]
limit = [[1, 1] for _ in range(n + 1)]
free = [[1, 1] for _ in range(n + 1)]
for (u, v) in lst:
	edge[u].append(v)
	edge[v].append(u)
queue = []
candidate = []
x = 1
queue.append([x, 0])
while len(queue) > 0:
	(u, pre) = queue[0]
	queue.pop(0)
	candidate.append([u, pre])
	for v in edge[u]:
		if v == pre:
			continue
		queue.append([v, u])
for (u, pre) in candidate[::-1]:
	for v in edge[u]:
		if v == pre:
			continue
		limit[u][0] = limit[u][0] * free[v][1] % MOD
		limit[u][1] = limit[u][1] * free[v][0] % MOD
		free[u][0] = free[u][0] * (free[v][0] + free[v][1] + limit[v][0]) % MOD
		free[u][1] = free[u][1] * (free[v][0] + free[v][1] + limit[v][1]) % MOD
	free[u][0] = (free[u][0] - limit[u][0] + MOD) % MOD
	free[u][1] = (free[u][1] - limit[u][1] + MOD) % MOD
print((free[x][0] + free[x][1]) % MOD)


from collections import defaultdict
n = int(input())
mod = 10 ** 9 + 7
graph = defaultdict(list)
for i in range(n - 1):
	(u, v) = [int(x) for x in input().split()]
	graph[u].append(v)
	graph[v].append(u)
depth = {1: 0}
nodes_at_depth = defaultdict(list)
nodes_at_depth[0] = [1]
visit = [1]
while visit:
	node = visit.pop(0)
	for child in graph[node]:
		if child not in depth:
			depth[child] = depth[node] + 1
			nodes_at_depth[depth[node] + 1].append(child)
			visit.append(child)
for node in range(1, n + 1):
	graph[node] = [x for x in graph[node] if depth[x] >= depth[node]]
val = {}
for d in sorted(nodes_at_depth, reverse=True):
	for node in nodes_at_depth[d]:
		if not graph[node]:
			val[node] = (1, 0)
			continue
		res = 1
		all_diff = 1
		for child in graph[node]:
			(a, b) = val[child]
			res *= a + b
			all_diff *= b
			res %= mod
			all_diff %= mod
		val[node] = (res % mod, (res - all_diff) % mod)
print(val[1][1] * 2 % mod)


import sys
sys.setrecursionlimit(10 ** 6)
n = int(input())
g = [[] for i in range(n)]
for i in range(n - 1):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	g[a].append(b)
	g[b].append(a)
MOD = 1000000007
res = [[-1 for j in range(2)] for i in range(n)]

def getRes(root, parent, good):
	if res[root][good] != -1:
		return res[root][good]
	if len(g[root]) == 0:
		return 1
	if len(g[root]) == 1:
		if g[root][0] == parent:
			res[root][1] = 0
			res[root][0] = 1
			return res[root][good]
	onlyRed = 1
	bothColors = 1
	for i in g[root]:
		if i == parent:
			continue
		childRes = getRes(i, root, 1)
		onlyRed *= childRes
		onlyRed %= MOD
		bothColors *= getRes(i, root, 0) + childRes * 2
		bothColors %= MOD
	atLeastOneBlue = bothColors + MOD - onlyRed
	atLeastOneBlue %= MOD
	res[root][1] = atLeastOneBlue
	res[root][0] = onlyRed
	return res[root][good]
l = [(0, -1)]
done = set()
done.add(0)
ind = 0
while len(l) < n:
	cur = l[ind][0]
	for i in g[cur]:
		if not i in done:
			done.add(i)
			l.append((i, cur))
	ind += 1
for i in range(n - 1, -1, -1):
	getRes(l[i][0], l[i][1], 1)
print(getRes(0, -1, 1) * 2 % MOD)


from functools import reduce
import operator

class KingdomTree:

	def __init__(self, number):
		self.name = number
		self.parent = None
		self.children = []
		self.divisions = None
		self.divisions_alone = None

	def connect(self, other):
		if other != self.parent:
			self.children.append(other)
			other.parent = self

	def get_divisions(self):
		if self.children:
			return self.divisions * 2
		else:
			return self.divisions_alone * 2

def adj_list_to_tree(adj_list, cities):
	stack = [1]
	while stack:
		u = stack.pop()
		parent = cities[u]
		for v in adj_list[u]:
			parent.connect(cities[v])
		stack.extend([city.name for city in parent.children])

def prod_modulo(x, y):
	base = 1000000007
	return x * y % base

def kingdom_divide(root):
	base = 1000000007
	stack = [root]
	while stack:
		city = stack.pop()
		if city.children:
			if city.children[0].divisions is None:
				stack.append(city)
				stack.extend(city.children)
			else:
				children_divisions = [c.divisions for c in city.children]
				children_divisions_combined = [(2 * c.divisions + c.divisions_alone) % base for c in city.children]
				city.divisions_alone = reduce(prod_modulo, children_divisions, 1)
				city.divisions = (reduce(prod_modulo, children_divisions_combined, 1) - city.divisions_alone) % base
		else:
			city.divisions = 0
			city.divisions_alone = 1
n = int(input().strip())
cities = [None] + [KingdomTree(i) for i in range(1, n + 1)]
adj_list = [[] for i in range(n + 1)]
for i in range(n - 1):
	(u, v) = tuple(map(int, input().strip().split(' ')))
	adj_list[u].append(v)
	adj_list[v].append(u)
adj_list_to_tree(adj_list, cities)
root = cities[1]
kingdom_divide(root)
print(root.get_divisions() % 1000000007)


n = int(input().strip())
lst = [[] for _ in range(n)]
v_lst = [0 for _ in range(n)]
for _ in range(n - 1):
	(u, v) = map(int, input().strip().split(' '))
	u -= 1
	v -= 1
	lst[u].append(v)
	lst[v].append(u)
slst = [0]
for i in range(n):
	curr_n = slst[i]
	for el in lst[curr_n]:
		lst[el].remove(curr_n)
		slst.append(el)
clst = [[0, 0] for _ in range(n)]
for i in range(len(slst) - 1, -1, -1):
	par = slst[i]
	same = 1
	nsame = 1
	for child in lst[par]:
		nsame *= clst[child][1]
		same *= 2 * clst[child][1] + clst[child][0]
		same %= 10 ** 9 + 7
		nsame %= 10 ** 9 + 7
	same -= nsame
	clst[par][0] = nsame
	clst[par][1] = same
print(clst[0][1] * 2 % (10 ** 9 + 7))


def bfs(graph, start, parent, child):
	parent[start] = 0
	(visited, queue, queue_record) = (set(), [start], [start])
	while queue:
		vertex = queue.pop(0)
		if vertex not in visited:
			temp = graph[vertex] - visited
			visited.add(vertex)
			queue.extend(temp)
			queue_record.extend(temp)
			for x in temp:
				if parent[x] == -1:
					parent[x] = vertex
					child[vertex].add(x)
	return queue_record
n = int(input())
graph = {}
parent = {}
child = {}
same = {}
diff = {}
rem = 10 ** 9 + 7
for i in range(1, n + 1):
	graph[i] = set()
	parent[i] = -1
	child[i] = set()
	same[i] = 1
	diff[i] = 1
for i in range(n - 1):
	(s, e) = input().split()
	[s, e] = list(map(int, [s, e]))
	graph[s].add(e)
	graph[e].add(s)
queue = bfs(graph, 1, parent, child)
queue = queue[::-1]
for x in queue:
	for y in child[x]:
		same[x] = same[x] * diff[y] % rem
	for y in child[x]:
		diff[x] = diff[x] * (same[y] + 2 * diff[y]) % rem
	diff[x] = (diff[x] - same[x] + rem) % rem
print(2 * diff[1] % rem)


from collections import defaultdict
from functools import reduce
import sys
N = int(input())
connections = sorted([tuple(sorted(list(map(int, input().split())))) for _ in range(N - 1)])
neighbors = defaultdict(lambda : set())
for (x, y) in connections:
	neighbors[x].add(y)
	neighbors[y].add(x)
ranks = [{1}]
taken = {1}
while True:
	curr_level = ranks[-1]
	next_level = set()
	for n in curr_level:
		next_level |= {z for z in neighbors[n] if not z in taken}
	ranks.append(next_level)
	taken |= next_level
	if not next_level:
		break
values = [None for _ in range(N + 1)]
MOD = 10 ** 9 + 7
l1 = lambda x, y: x * values[y][0] % MOD
l2 = lambda x, y: x * (values[y][0] * 2 + values[y][1]) % MOD
for i in range(len(ranks) - 2, -1, -1):
	level = ranks[i]
	for n in level:
		nextn = {z for z in neighbors[n] if z in ranks[i + 1]}
		if not nextn:
			values[n] = (0, 1)
			continue
		bad = reduce(l1, nextn, 1)
		good = reduce(l2, nextn, 1)
		good -= bad
		values[n] = (good, bad)
print(values[1][0] * 2 % MOD)


from functools import reduce, lru_cache, wraps
import operator as op
M = 10 ** 9 + 7
product = lambda xs: reduce(op.mul, xs, 1)
from collections import defaultdict

def solve(n, roads):
	adjs = defaultdict(set)
	for (u, v) in roads:
		adjs[u].add(v)
		adjs[v].add(u)

	@memoized_trampoline
	def recurse(i, last, issame):
		neighbors = adjs[i] - {last}
		if not neighbors:
			return int(issame)
		nbrec = []
		for nb in neighbors:
			nbrec.append([(yield (nb, i, True)), (yield (nb, i, False))])
		recsame = product(map(sum, nbrec))
		recnot = product(map(op.itemgetter(1), nbrec))
		if issame:
			rv = recsame
		else:
			rv = recsame - recnot
		return rv % M
	return recurse(1, None, False) * 2

def memoized_trampoline(f):
	memo = {}

	@wraps(f)
	def g(*args):
		stack = [[args, f(*args)]]
		lastmsg = None
		while stack:
			(args, top) = stack[-1]
			try:
				args1 = top.send(lastmsg)
			except StopIteration as e:
				lastmsg = e.value
				memo[args] = lastmsg
				stack.pop()
				continue
			try:
				lastmsg = memo[args1]
			except KeyError:
				lastmsg = None
				stack.append([args1, f(*args1)])
		return lastmsg
	return g

def readints():
	return list(map(int, input().split()))
n = int(input())
roads = [readints() for _ in range(n - 1)]
print(solve(n, roads) % M)


from collections import defaultdict, Counter, deque

def tree():
	return defaultdict(list)
MOD = 1000000007

def get_splits(kingdom):
	s = set()
	for city in kingdom:
		if len(kingdom[city]) == 1:
			continue
		for neighbor in kingdom[city]:
			if len(kingdom[neighbor]) == 1:
				continue
			s.add((city, neighbor) if city < neighbor else (neighbor, city))
	return list(s)

def divisions(kingdom, splits, j=0, ignore=Counter()):
	n = 2
	for i in range(j, len(splits)):
		(u, v) = splits[i]
		if not ignore[u] + 1 < len(kingdom[u]):
			continue
		if not ignore[v] + 1 < len(kingdom[v]):
			continue
		n = (n + divisions(kingdom, splits, i + 1, ignore + Counter([u, v]))) % MOD
	return n
n = int(input())
kingdom = defaultdict(list)
for _ in range(n - 1):
	(u, v) = map(int, input().split())
	kingdom[u].append(v)
	kingdom[v].append(u)
cities = []
keys = deque([1])
while keys:
	key = keys.popleft()
	cities.append(key)
	neighbors = kingdom.get(key)
	for neighbor in neighbors:
		kingdom[neighbor].remove(key)
	keys.extend(neighbors)
sums = defaultdict(list)
for i in reversed(cities):
	if not kingdom[i]:
		sums[i] = [1, 0, 1, 0]
		continue
	(rr, rb, bb, br) = (1, 1, 1, 1)
	(rb_c, br_c) = (1, 1)
	for j in kingdom[i]:
		rr = rr * (sums[j][0] % MOD + sums[j][3] % MOD) % MOD
		rb = rb * (sums[j][0] % MOD + sums[j][3] % MOD) % MOD
		bb = bb * (sums[j][1] % MOD + sums[j][2] % MOD) % MOD
		br = br * (sums[j][1] % MOD + sums[j][2] % MOD) % MOD
		br_c = br_c * sums[j][1] % MOD
		rb_c = rb_c * sums[j][3] % MOD
	sums[i] = [rr, (rb - rb_c) % MOD, bb, (br - br_c) % MOD]
print((sums[1][1] + sums[1][3]) % MOD)


import queue
N = int(input())
tree = {n: set() for n in range(N)}
parent = dict()
nchildren = {n: list() for n in range(N)}
n1 = {n: list() for n in range(N)}
n2 = {n: list() for n in range(N)}
for n in range(N - 1):
	(i, j) = [int(x) for x in input().strip().split(' ')]
	tree[i - 1].add(j - 1)
	tree[j - 1].add(i - 1)
root = 0
modulo = 1000000007
nodes = queue.deque()
nodes.appendleft(root)
while nodes:
	cur_node = nodes[0]
	if tree[cur_node]:
		child = tree[cur_node].pop()
		tree[child].remove(cur_node)
		parent[child] = cur_node
		nodes.appendleft(child)
	else:
		nodes.popleft()
		n1c = 1
		n2c = 0
		ncc = 0
		for i in range(len(n1[cur_node])):
			if nchildren[cur_node][i] > 0:
				n1c = n1c * (2 * n1[cur_node][i] + n2[cur_node][i]) % modulo
				if n2c == 0:
					n2c = n1[cur_node][i]
				else:
					n2c = n2c * n1[cur_node][i] % modulo
				ncc = ncc + 1
		if ncc != len(n1[cur_node]):
			n2c = 0
		if cur_node in parent:
			n1[parent[cur_node]].append(n1c - n2c)
			n2[parent[cur_node]].append(n2c)
			nchildren[parent[cur_node]].append(len(n1[cur_node]))
print(2 * (n1c - n2c) % modulo)


from collections import namedtuple, deque
N = int(input())
nodes = []
k = int(10 ** 9 + 7)

class Node:

	def __init__(self):
		self.id = 0
		self.children = set()
nodes = []
for i in range(N):
	nodes.append(Node())
for _ in range(N - 1):
	(a, b) = map(int, input().split())
	(a, b) = (a - 1, b - 1)
	nodes[a].children.add(nodes[b])
	nodes[b].children.add(nodes[a])

def remove_backward(root):
	q = deque([root])
	while q:
		node = q.popleft()
		node.id = id
		for c in node.children:
			c.children.remove(node)
		q.extend(node.children)
remove_backward(nodes[0])
BLUE = 1
RED = ~BLUE

def label_nodes(root):
	q = deque([root])
	id = 0
	while q:
		node = q.popleft()
		node.id = id
		id += 1
		q.extend(node.children)
label_nodes(nodes[0])
nodes = sorted(nodes, key=lambda x: x.id, reverse=True)
OPT = []
for i in range(N):
	OPT.append([])
	for j in range(2):
		OPT[i].append([])
		for l in range(2):
			OPT[i][j].append(0)
for node in nodes:
	if not node.children:
		for color in [BLUE, RED]:
			for parent_color in [BLUE, RED]:
				r = 1 if color == parent_color else 0
				OPT[node.id][color][parent_color] = r % k
	else:
		for color in [BLUE, RED]:
			for parent_color in [BLUE, RED]:
				if color == parent_color:
					p = 1
					for c in node.children:
						m = sum([OPT[c.id][z][color] for z in [BLUE, RED]])
						p *= m
					r = p
				else:
					p1 = 1
					for c in node.children:
						m = sum([OPT[c.id][z][color] for z in [BLUE, RED]])
						p1 *= m
					p2 = 1
					for c in node.children:
						p2 *= OPT[c.id][~color][color]
					r = p1 - p2
				OPT[node.id][color][parent_color] = r % k
solution = sum([OPT[0][z][~z] for z in [BLUE, RED]])
print(solution % k)


import sys
import operator
from functools import reduce

class Tree:

	def __init__(self, label):
		self.label = label
		self.children = []
		self.visited = False
		self.b_bounded = 0
		self.b_singleton = 0
		self.y_bounded = 0
		self.y_singleton = 0

	def update(self):
		if not self.children:
			(self.b_bounded, self.b_singleton, self.y_bounded, self.y_singleton) = (0, 1, 0, 1)
			return (self.b_bounded, self.b_singleton, self.y_bounded, self.y_singleton)

def product(iterable):
	return reduce(operator.mul, iterable, 1)

def buildKingdom(n, roads):
	connections = {0: []}
	connections.update({i: [] for i in range(1, n + 1)})
	for road in roads:
		connections[road[0]].append(road[1])
		connections[road[1]].append(road[0])
	kingdom = [Tree(i) for i in range(n + 1)]
	stack = []
	stack.append(kingdom[1])
	while stack:
		v = stack.pop()
		if not v.visited:
			v.visited = True
			for c in connections[v.label]:
				if not kingdom[c].visited:
					v.children.append(kingdom[c])
					stack.append(kingdom[c])
			v.update()
	return kingdom

def calculateWays(tree):
	parents = []
	notepad = []
	parents.append(tree)
	notepad.append([])
	while parents:
		last = parents[-1]
		if last.children:
			parents.append(last.children.pop())
			notepad.append([])
		else:
			parents.pop()
			lastPad = notepad.pop()
			if not lastPad:
				notepad[-1].append((last.b_bounded, last.b_singleton, last.y_bounded, last.y_singleton))
			else:
				b_bounded = (product([u[0] + u[1] + u[2] for u in lastPad]) - product([u[2] for u in lastPad])) % (10 ** 9 + 7)
				b_singleton = product([u[2] for u in lastPad]) % (10 ** 9 + 7)
				y_bounded = (product([u[0] + u[2] + u[3] for u in lastPad]) - product([u[0] for u in lastPad])) % (10 ** 9 + 7)
				y_singleton = product([u[0] for u in lastPad]) % (10 ** 9 + 7)
				if notepad:
					notepad[-1].append((b_bounded, b_singleton, y_bounded, y_singleton))
				else:
					notepad.append((b_bounded, b_singleton, y_bounded, y_singleton))
	return notepad

def kingdomDivision(n, roads):
	kingdom = buildKingdom(n, roads)
	(b_bounded, b_singleton, y_bounded, y_singleton) = calculateWays(kingdom[1])[0]
	return (b_bounded + y_bounded) % (10 ** 9 + 7)
n = int(input().strip())
roads = []
for roads_i in range(n - 1):
	roads_t = [int(roads_temp) for roads_temp in input().strip().split(' ')]
	roads.append(roads_t)
result = kingdomDivision(n, roads)
print(result)


from collections import defaultdict, Counter, deque
mod = 10 ** 9 + 7
n = int(input())
(edges, degree) = (defaultdict(set), Counter())
for _ in range(n - 1):
	(u, v) = map(int, input().split())
	edges[u].add(v)
	edges[v].add(u)
	degree[u] += 1
	degree[v] += 1
count = {u: {True: 1, False: 1} for u in degree}
leaves = deque([u for u in degree if degree[u] == 1])
while leaves:
	node = leaves.popleft()
	count[node][False] = count[node][True] - count[node][False]
	if not degree[node]:
		root = node
		break
	parent = edges[node].pop()
	edges[parent].discard(node)
	degree[parent] -= 1
	if degree[parent] == 1:
		leaves.append(parent)
	count[parent][True] *= count[node][True] + count[node][False]
	count[parent][False] *= count[node][False]
ways = 2 * count[root][0]
print(ways % mod)


import sys
from collections import defaultdict, Counter, deque
n = int(input())
edges = defaultdict(set)
degree = Counter()
for _ in range(n - 1):
	(u, v) = map(int, input().split())
	edges[u].add(v)
	edges[v].add(u)
	degree[u] += 1
	degree[v] += 1
count = {u: {True: 1, False: 1} for u in degree}
leaves = deque([u for u in degree if degree[u] == 1])
while True:
	node = leaves.popleft()
	count[node][False] = count[node][True] - count[node][False]
	if not degree[node]:
		root = node
		break
	else:
		parent = edges[node].pop()
		edges[parent].discard(node)
		degree[parent] -= 1
		if degree[parent] == 1:
			leaves.append(parent)
		count[parent][True] *= count[node][True] + count[node][False]
		count[parent][False] *= count[node][False]
total = 2 * count[root][0]
print(total % (10 ** 9 + 7))


from collections import defaultdict, Counter, deque
n = int(input())
edges = defaultdict(set)
degree = Counter()
for _ in range(n - 1):
	(u, v) = map(int, input().split())
	edges[u].add(v)
	edges[v].add(u)
	degree[u] += 1
	degree[v] += 1
count = {u: {True: 1, False: 1} for u in degree}
leaves = deque([u for u in degree if degree[u] == 1])
while True:
	node = leaves.popleft()
	count[node][False] = count[node][True] - count[node][False]
	if not degree[node]:
		root = node
		break
	else:
		parent = edges[node].pop()
		edges[parent].discard(node)
		degree[parent] -= 1
		if degree[parent] == 1:
			leaves.append(parent)
		count[parent][True] *= count[node][True] + count[node][False]
		count[parent][False] *= count[node][False]
total = 2 * count[root][0]
print(total % (10 ** 9 + 7))


import sys
prime = 1000000007

def kingdomDivision(graph, n):
	leaves = []
	for i in range(n):
		if len(graph[i][2]) == 1:
			leaves.append(i)
	while len(leaves) != 1:
		nextleaves = []
		for i in leaves:
			x = (prime + graph[i][1] - graph[i][0]) % prime
			y = graph[i][1]
			if len(graph[i][2]) == 0:
				nextleaves.append(i)
				continue
			j = graph[i][2].pop()
			graph[j][0] = graph[j][0] * x % prime
			graph[j][1] = graph[j][1] * ((x + y) % prime) % prime
			graph[j][2].remove(i)
			if len(graph[j][2]) == 1:
				nextleaves.append(j)
		leaves = nextleaves
	ik = leaves[0]
	ans = (prime + graph[ik][1] - graph[ik][0]) % prime
	return (ans + ans) % prime
n = int(input().strip())
roads = [[1, 1, set()] for i in range(n)]
for roads_i in range(n - 1):
	roads_t = [int(roads_temp) for roads_temp in input().strip().split(' ')]
	roads[roads_t[0] - 1][2].add(roads_t[1] - 1)
	roads[roads_t[1] - 1][2].add(roads_t[0] - 1)
print(kingdomDivision(roads, n))


from collections import defaultdict, Counter, deque
n = int(input())
edges = defaultdict(set)
degree = Counter()
for _ in range(n - 1):
	(u, v) = map(int, input().split())
	edges[u].add(v)
	edges[v].add(u)
	degree[u] += 1
	degree[v] += 1
count = {u: {True: 1, False: 1} for u in degree}
leaves = deque([u for u in degree if degree[u] == 1])
while True:
	node = leaves.popleft()
	count[node][False] = count[node][True] - count[node][False]
	if not degree[node]:
		root = node
		break
	else:
		parent = edges[node].pop()
		edges[parent].discard(node)
		degree[parent] -= 1
		if degree[parent] == 1:
			leaves.append(parent)
		count[parent][True] *= count[node][True] + count[node][False]
		count[parent][False] *= count[node][False]
total = 2 * count[root][0]
print(total % (10 ** 9 + 7))


from collections import defaultdict, Counter, deque
n = int(input())
e = defaultdict(set)
d = Counter()
for _ in range(n - 1):
	(u, v) = map(int, input().split())
	e[u].add(v)
	e[v].add(u)
	d[u] += 1
	d[v] += 1
count = {u: {True: 1, False: 1} for u in d}
l = deque([u for u in d if d[u] == 1])
while True:
	node = l.popleft()
	count[node][False] = count[node][True] - count[node][False]
	if not d[node]:
		root = node
		break
	else:
		p = e[node].pop()
		e[p].discard(node)
		d[p] -= 1
		if d[p] == 1:
			l.append(p)
		count[p][True] *= count[node][True] + count[node][False]
		count[p][False] *= count[node][False]
total = 2 * count[root][0]
print(total % (10 ** 9 + 7))


from collections import defaultdict, Counter, deque
n = int(input())
edges = defaultdict(set)
degree = Counter()
for _ in range(n - 1):
	(u, v) = map(int, input().split())
	edges[u].add(v)
	edges[v].add(u)
	degree[u] += 1
	degree[v] += 1
count = {u: {True: 1, False: 1} for u in degree}
leaves = deque([u for u in degree if degree[u] == 1])
while True:
	node = leaves.popleft()
	count[node][False] = count[node][True] - count[node][False]
	if not degree[node]:
		root = node
		break
	else:
		parent = edges[node].pop()
		edges[parent].discard(node)
		degree[parent] -= 1
		if degree[parent] == 1:
			leaves.append(parent)
		count[parent][True] *= count[node][True] + count[node][False]
		count[parent][False] *= count[node][False]
total = 2 * count[root][0]
print(total % (10 ** 9 + 7))


P = 10 ** 9 + 7

def prod(x):
	r = 1
	for i in x:
		r *= i
	return r

def kingdomDivision(n, edges):
	adj = [[] for _ in range(n)]
	for (x, y) in edges:
		adj[x - 1].append(y - 1)
		adj[y - 1].append(x - 1)
	if n == 2:
		return 1
	for i in range(n):
		if len(adj[i]) > 1:
			start = i
			break
	cache = {}
	stack = [(start, -1, False)]
	while stack:
		(node, parent, friendly_border) = stack.pop()
		is_safe = friendly_border
		wait_for_children = False
		relevant_children = set()
		for child in adj[node]:
			if child == parent:
				continue
			elif len(adj[child]) == 1:
				is_safe = True
			elif not wait_for_children and (child, node, False) not in cache:
				stack.append((node, parent, friendly_border))
				stack.append((child, node, False))
				stack.append((child, node, True))
				wait_for_children = True
			elif wait_for_children:
				stack.append((child, node, False))
				stack.append((child, node, True))
			else:
				relevant_children.add(child)
		if not wait_for_children:
			if not relevant_children:
				cache[node, parent, friendly_border] = 1
			else:
				if any(((child, node, 0) not in cache for child in relevant_children)):
					print(node, parent, adj[node], child)
				all_comb = prod((sum((cache[child, node, b] for b in range(2))) for child in relevant_children))
				if is_safe:
					cache[node, parent, friendly_border] = all_comb % P
				else:
					cache[node, parent, friendly_border] = (all_comb - prod((cache[child, node, False] for child in relevant_children))) % P
	return 2 * cache[start, -1, False] % P
n = int(input().strip())
roads = []
for roads_i in range(n - 1):
	roads_t = [int(roads_temp) for roads_temp in input().strip().split(' ')]
	roads.append(roads_t)
result = kingdomDivision(n, roads)
print(result)


import sys

def subtree(roads, root, parent):
	new_roads = dict([(i, set([])) for i in range(1, len(roads) + 1)])
	queue = [root]
	seen = set([])
	while queue:
		node = queue.pop(0)
		seen.add(node)
		for n in roads[node]:
			if n != parent and n not in seen and (n != 'leaf'):
				new_roads[node].add(n)
				new_roads[n].add(node)
				queue.append(n)
	return new_roads

def helper(r, root, parent):
	if parent != None and len(r[root]) == 1:
		return (1, 0, 0, 1)
	child_counts = []
	for child in r[root]:
		if parent == None or child != parent:
			child_count = helper(r, child, root)
			child_counts.append(child_count)
	rr = 1
	rb = 1
	br = 1
	bb = 1
	for c in child_counts:
		rr *= c[0] + c[1]
		br *= c[0] + c[1]
		rb *= c[2] + c[3]
		bb *= c[2] + c[3]
		rr %= 10 ** 9 + 7
		br %= 10 ** 9 + 7
		rb %= 10 ** 9 + 7
		bb %= 10 ** 9 + 7
	all_red = 1
	all_black = 1
	for c in child_counts:
		all_red *= c[2]
		all_black *= c[1]
		all_red %= 10 ** 9 + 7
		all_black %= 10 ** 9 + 7
	rb -= all_red
	br -= all_black
	return (rr, rb, br, bb)

def helper2(r, root):
	values = {}
	layers = []
	queue = [(root, 0)]
	seen = set([])
	while queue:
		node = queue.pop(0)
		if len(layers) < node[1] + 1:
			layers.append([])
		layers[-1].append(node[0])
		seen.add(node[0])
		for n in r[node[0]]:
			if n not in seen:
				queue.append((n, node[1] + 1))
	for l in layers[-1]:
		values[l] = (1, 0, 0, 1)
	for l in layers[-2::-1]:
		for node in l:
			child_counts = []
			test = 0
			for child in r[node]:
				if child in values:
					child_counts.append(values[child])
				else:
					test += 1
			rr = 1
			rb = 1
			br = 1
			bb = 1
			for c in child_counts:
				rr *= c[0] + c[1]
				br *= c[0] + c[1]
				rb *= c[2] + c[3]
				bb *= c[2] + c[3]
				rr %= 10 ** 9 + 7
				br %= 10 ** 9 + 7
				rb %= 10 ** 9 + 7
				bb %= 10 ** 9 + 7
			all_red = 1
			all_black = 1
			for c in child_counts:
				all_red *= c[2]
				all_black *= c[1]
				all_red %= 10 ** 9 + 7
				all_black %= 10 ** 9 + 7
			rb -= all_red
			br -= all_black
			values[node] = (rr, rb, br, bb)
	return values[root]

def kingdomDivision(n, roads):
	r = dict([(i, set([])) for i in range(1, n + 1)])
	for road in roads:
		r[road[0]].add(road[1])
		r[road[1]].add(road[0])
	result = helper2(r, 1)
	return (result[1] + result[2]) % (10 ** 9 + 7)
n = int(input().strip())
roads = []
for roads_i in range(n - 1):
	roads_t = [int(roads_temp) for roads_temp in input().strip().split(' ')]
	roads.append(roads_t)
result = kingdomDivision(n, roads)
print(result)


from collections import defaultdict, Counter, deque
n = int(input())
edges = defaultdict(set)
degree = Counter()
for _ in range(n - 1):
	(u, v) = map(int, input().split())
	edges[u].add(v)
	edges[v].add(u)
	degree[u] += 1
	degree[v] += 1
count = {u: {True: 1, False: 1} for u in degree}
leaves = deque([u for u in degree if degree[u] == 1])
while True:
	node = leaves.popleft()
	count[node][False] = count[node][True] - count[node][False]
	if not degree[node]:
		root = node
		break
	else:
		parent = edges[node].pop()
		edges[parent].discard(node)
		degree[parent] -= 1
		if degree[parent] == 1:
			leaves.append(parent)
		count[parent][True] *= count[node][True] + count[node][False]
		count[parent][False] *= count[node][False]
total = 2 * count[root][0]
print(total % (10 ** 9 + 7))


from collections import defaultdict, deque, Counter
MOD = 10 ** 9 + 7
n = int(input().strip())
roads = defaultdict(set)
node_level = Counter()
for _ in range(n - 1):
	(u, v) = map(int, input().strip().split())
	roads[u].add(v)
	roads[v].add(u)
	node_level[u] += 1
	node_level[v] += 1
count = {u: {'red': 1, 'blue': 1} for u in node_level}
leaves = deque([node for node in node_level if node_level[node] == 1])
while True:
	node = leaves.popleft()
	count[node]['blue'] = count[node]['red'] - count[node]['blue']
	if not node_level[node]:
		root = node
		break
	else:
		parent = roads[node].pop()
		roads[parent].remove(node)
		node_level[parent] -= 1
		if node_level[parent] == 1:
			leaves.append(parent)
		count[parent]['red'] *= count[node]['red'] + count[node]['blue']
		count[parent]['blue'] *= count[node]['blue']
print(2 * count[root]['blue'] % MOD)


n = int(input())
roads = [[] for i in range(n + 1)]
for i in range(n - 1):
	(u, v) = map(int, input().split())
	roads[u].append(v)
	roads[v].append(u)
mod = 10 ** 9 + 7
active = [1]
visited = [0] * (n + 1)
a = [1] * (n + 1)
b = [1] * (n + 1)
while active:
	i = active.pop()
	if visited[i]:
		for j in roads[i]:
			a[i] = a[i] * (a[j] + b[j]) % mod
			b[i] = b[i] * b[j] % mod
		b[i] = (a[i] - b[i]) % mod
	else:
		visited[i] = 1
		roads[i] = [j for j in roads[i] if not visited[j]]
		active.append(i)
		active.extend(roads[i])
print(2 * b[1] % mod)


from collections import defaultdict, Counter, deque
n = int(input())
edges = defaultdict(set)
degree = Counter()
for _ in range(n - 1):
	(u, v) = map(int, input().split())
	edges[u].add(v)
	edges[v].add(u)
	degree[u] += 1
	degree[v] += 1
count = {u: {True: 1, False: 1} for u in degree}
leaves = deque([u for u in degree if degree[u] == 1])
while True:
	node = leaves.popleft()
	count[node][False] = count[node][True] - count[node][False]
	if not degree[node]:
		root = node
		break
	else:
		parent = edges[node].pop()
		edges[parent].discard(node)
		degree[parent] -= 1
		if degree[parent] == 1:
			leaves.append(parent)
		count[parent][True] *= count[node][True] + count[node][False]
		count[parent][False] *= count[node][False]
total = 2 * count[root][0]
print(total % (10 ** 9 + 7))


from collections import defaultdict, Counter, deque
n = int(input())
edges = defaultdict(set)
degree = Counter()
for _ in range(n - 1):
	(u, v) = map(int, input().split())
	edges[u].add(v)
	edges[v].add(u)
	degree[u] += 1
	degree[v] += 1
count = {u: {True: 1, False: 1} for u in degree}
leaves = deque([u for u in degree if degree[u] == 1])
while True:
	node = leaves.popleft()
	count[node][False] = count[node][True] - count[node][False]
	if not degree[node]:
		root = node
		break
	else:
		parent = edges[node].pop()
		edges[parent].discard(node)
		degree[parent] -= 1
		if degree[parent] == 1:
			leaves.append(parent)
		count[parent][True] *= count[node][True] + count[node][False]
		count[parent][False] *= count[node][False]
total = 2 * count[root][0]
print(total % (10 ** 9 + 7))


from collections import defaultdict, Counter, deque
n = int(input())
edges = defaultdict(set)
degree = Counter()
for _ in range(n - 1):
	(u, v) = map(int, input().split())
	edges[u].add(v)
	edges[v].add(u)
	degree[u] += 1
	degree[v] += 1
count = {u: {True: 1, False: 1} for u in degree}
leaves = deque([u for u in degree if degree[u] == 1])
while True:
	node = leaves.popleft()
	count[node][False] = count[node][True] - count[node][False]
	if not degree[node]:
		root = node
		break
	else:
		parent = edges[node].pop()
		edges[parent].discard(node)
		degree[parent] -= 1
		if degree[parent] == 1:
			leaves.append(parent)
		count[parent][True] *= count[node][True] + count[node][False]
		count[parent][False] *= count[node][False]
total = 2 * count[root][0]
print(total % (10 ** 9 + 7))


from collections import defaultdict, Counter, deque
n = int(input())
edges = defaultdict(set)
degree = Counter()
for _ in range(n - 1):
	(u, v) = map(int, input().split())
	edges[u].add(v)
	edges[v].add(u)
	degree[u] += 1
	degree[v] += 1
count = {u: {True: 1, False: 1} for u in degree}
leaves = deque([u for u in degree if degree[u] == 1])
while True:
	node = leaves.popleft()
	count[node][False] = count[node][True] - count[node][False]
	if not degree[node]:
		root = node
		break
	else:
		parent = edges[node].pop()
		edges[parent].discard(node)
		degree[parent] -= 1
		if degree[parent] == 1:
			leaves.append(parent)
		count[parent][True] *= count[node][True] + count[node][False]
		count[parent][False] *= count[node][False]
total = 2 * count[root][0]
print(total % (10 ** 9 + 7))


import sys
n = int(input().strip())
lst = [[] for _ in range(n)]
v_lst = [0 for _ in range(n)]
for _ in range(n - 1):
	(u, v) = map(int, input().strip().split(' '))
	u -= 1
	v -= 1
	lst[u].append(v)
	lst[v].append(u)
slst = [0]
for i in range(n):
	curr_n = slst[i]
	for el in lst[curr_n]:
		lst[el].remove(curr_n)
		slst.append(el)
clst = [[0, 0] for _ in range(n)]
for i in range(len(slst) - 1, -1, -1):
	par = slst[i]
	same = 1
	nsame = 1
	for child in lst[par]:
		nsame *= clst[child][1]
		same *= 2 * clst[child][1] + clst[child][0]
		same %= 10 ** 9 + 7
		nsame %= 10 ** 9 + 7
	same -= nsame
	clst[par][0] = nsame
	clst[par][1] = same
print(clst[0][1] * 2 % (10 ** 9 + 7))


from collections import defaultdict, Counter, deque
n = int(input())
edges = defaultdict(set)
degree = Counter()
for _ in range(n - 1):
	(u, v) = map(int, input().split())
	edges[u].add(v)
	edges[v].add(u)
	degree[u] += 1
	degree[v] += 1
count = {u: {True: 1, False: 1} for u in degree}
leaves = deque([u for u in degree if degree[u] == 1])
while True:
	node = leaves.popleft()
	count[node][False] = count[node][True] - count[node][False]
	if not degree[node]:
		root = node
		break
	else:
		parent = edges[node].pop()
		edges[parent].discard(node)
		degree[parent] -= 1
		if degree[parent] == 1:
			leaves.append(parent)
		count[parent][True] *= count[node][True] + count[node][False]
		count[parent][False] *= count[node][False]
total = 2 * count[root][0]
print(total % (10 ** 9 + 7))


from functools import reduce
N = int(1000000000.0) + 7

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

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

class Node:

	def __init__(self, node_id):
		self.id = node_id
		self.children = []
		self.divisions = [0, 1]

	def product(self, *args):
		return reduce(mul, (reduce(add, (child.divisions[arg] for arg in args)) for child in self.children))

	def calculate_divisions(self):
		if not self.children:
			return
		v = self.product(0)
		self.divisions[0] = add(self.product(0, 0, 1), N - v)
		self.divisions[1] = v

	def make_string(self, level=0):
		return ' ' * level + str(self) + ''.join(('\n' + child.make_string(level + 1) for child in self.children))

	def __str__(self):
		return str(self.id) + ' ' + str(self.divisions)

class Tree:

	def __init__(self, edges):
		self.root = Node(1)
		stack = [(self.root, None)]
		while stack:
			(node, parent_id) = stack.pop()
			for child_id in edges[node.id]:
				if child_id != parent_id:
					node.children.append(Node(child_id))
			for c in node.children:
				stack.append((c, node.id))
		for node in reversed(list(self)):
			node.calculate_divisions()

	def __iter__(self):
		stack = [self.root]
		while stack:
			node = stack.pop()
			yield node
			stack += node.children

	def __str__(self):
		return self.root.make_string()
n = int(input())
edges = [[] for _ in range(n + 1)]
for _ in range(n - 1):
	(u, v) = (int(x) for x in input().split())
	edges[u].append(v)
	edges[v].append(u)
t = Tree(edges)
print(mul(2, t.root.divisions[0]))


module = 10 ** 9 + 7

def _mod(number):
	return number % module

def _prod(l):
	result = 1
	for item in l:
		result = _mod(result * item)
	return result

def kingdomDivision(n, roads):
	graph = {i + 1: list() for i in range(n)}
	for road in roads:
		(u, v) = (road[0], road[1])
		graph[u].append(v)
		graph[v].append(u)
	combs = dict()
	childs = dict()

	def do_topo_sort(u):
		treated = set()
		sorted = [u]
		index = 0
		while index < len(sorted):
			head = sorted[index]
			treated.add(head)
			index += 1
			children = [v for v in graph[head] if v not in treated]
			childs[head] = children
			sorted.extend(children)
		return sorted
	sorted_vertices = do_topo_sort(1)
	sorted_vertices.reverse()
	for u in sorted_vertices:
		children = childs[u]
		if not children:
			combs[u] = {'stable': 0, 'unstable': 1}
			continue
		unstable = _prod([combs[c]['stable'] for c in children])
		s1 = _prod([2 * combs[c]['stable'] + combs[c]['unstable'] for c in children])
		stable = _mod(s1 - unstable)
		combs[u] = {'stable': stable, 'unstable': unstable}
	if n == 1:
		return 2
	return _mod(2 * combs[1]['stable'])

def main():
	n = int(input())
	roads = []
	for _ in range(n - 1):
		roads.append(list(map(int, input().strip().split())))
	result = kingdomDivision(n, roads)
	print(result)
main()


import math
import os
import random
import re
import sys
from collections import defaultdict, Counter, deque

def kingdomDivision(n, roads_map):
	dic = defaultdict(set)
	node_count = Counter()
	for road in roads_map:
		(a, b) = road
		dic[a].add(b)
		dic[b].add(a)
		node_count[a] += 1
		node_count[b] += 1
	ways = {x: {0: 1, 1: 1} for x in dic}
	leafes = deque([x for x in node_count if node_count[x] == 1])
	while True:
		node = leafes.popleft()
		ways[node][0] = ways[node][1] - ways[node][0]
		if not node_count[node]:
			root = node
			break
		parent = dic[node].pop()
		ways[parent][1] *= ways[node][0] + ways[node][1]
		ways[parent][0] *= ways[node][0]
		dic[parent].discard(node)
		node_count[parent] -= 1
		if node_count[parent] == 1:
			leafes.append(parent)
	return ways[root][0] * 2 % (10 ** 9 + 7)
n = int(input())
roads_map = []
for _ in range(n - 1):
	roads_map.append(list(map(int, input().rstrip().split())))
print(kingdomDivision(n, roads_map))


from queue import deque

class Node:

	def __init__(self, id):
		(self.c1, self.c0, self.es, self.id) = (1, 1, [], id)
(q, M) = (deque(), 10 ** 9 + 7)
n = int(input())
nodes = [Node(i) for i in range(n + 1)]
for i in range(n - 1):
	(a, b) = map(int, input().split(' '))
	nodes[a].es.append(nodes[b])
	nodes[b].es.append(nodes[a])
q.clear()
for i in range(1, n + 1):
	if len(nodes[i].es) == 1:
		q.append(nodes[i])
while q:
	c = q.popleft()
	c.c0 = (c.c1 - c.c0) % M
	if not c.es:
		print((c.c0 << 1) % M)
		break
	for p in c.es:
		p.c0 = p.c0 * c.c0 % M
		p.c1 = p.c1 * (c.c0 + c.c1) % M
		for pc in range(len(p.es) - 1):
			if p.es[pc] == c:
				p.es[pc] = p.es[-1]
		p.es.pop()
		if len(p.es) < 2:
			q.append(p)


from collections import defaultdict, Counter, deque
n = int(input())
edges = defaultdict(set)
degree = Counter()
for _ in range(n - 1):
	(u, v) = map(int, input().split())
	edges[u].add(v)
	edges[v].add(u)
	degree[u] += 1
	degree[v] += 1
count = {u: {True: 1, False: 1} for u in degree}
leaves = deque([u for u in degree if degree[u] == 1])
while True:
	node = leaves.popleft()
	count[node][False] = count[node][True] - count[node][False]
	if not degree[node]:
		root = node
		break
	else:
		parent = edges[node].pop()
		edges[parent].discard(node)
		degree[parent] -= 1
		if degree[parent] == 1:
			leaves.append(parent)
		count[parent][True] *= count[node][True] + count[node][False]
		count[parent][False] *= count[node][False]
total = 2 * count[root][0]
print(total % (10 ** 9 + 7))


from collections import defaultdict, Counter, deque
n = int(input())
edges = defaultdict(set)
degree = Counter()
for _ in range(n - 1):
	(u, v) = map(int, input().split())
	edges[u].add(v)
	edges[v].add(u)
	degree[u] += 1
	degree[v] += 1
count = {u: {True: 1, False: 1} for u in degree}
leaves = deque([u for u in degree if degree[u] == 1])
while True:
	node = leaves.popleft()
	count[node][False] = count[node][True] - count[node][False]
	if not degree[node]:
		root = node
		break
	else:
		parent = edges[node].pop()
		edges[parent].discard(node)
		degree[parent] -= 1
		if degree[parent] == 1:
			leaves.append(parent)
		count[parent][True] *= count[node][True] + count[node][False]
		count[parent][False] *= count[node][False]
total = 2 * count[root][0]
print(total % (10 ** 9 + 7))


import math
import os
import random
import re
import sys

def kingdomDivision(n, roads):
	if __name__ == '__main__':
		fptr = open(os.environ['OUTPUT_PATH'], 'w')
		n = int(input())
		roads = []
		for _ in range(n - 1):
			roads.append(list(map(int, input().rstrip().split())))
		result = kingdomDivision(n, roads)
		fptr.write(str(result) + '\n')
		fptr.close()
n = int(input().strip())
NodeDict = {m: [] for m in range(n)}
for a0 in range(n - 1):
	(u, v) = input().strip().split(' ')
	(u, v) = [int(u) - 1, int(v) - 1]
	NodeDict[u].append(v)
	NodeDict[v].append(u)
M = int(1000000000.0 + 7)
ActiveSet = set()
for key in NodeDict:
	if len(NodeDict[key]) != 1:
		ActiveSet.add(key)
NodeDict2 = {m: None for m in ActiveSet}
TerminalNodes = []
for key in ActiveSet:
	NodeDict2[key] = [[], {('r', False): 0, ('b', False): 0, ('r', True): 0, ('b', True): 0}]
	for i1 in NodeDict[key]:
		if i1 in ActiveSet:
			NodeDict2[key][0].append(i1)
		else:
			NodeDict2[key][1]['r', True] = 1
			NodeDict2[key][1]['b', True] = 1
	if NodeDict2[key][1]['b', True] == 0:
		NodeDict2[key][1]['r', False] = 1
		NodeDict2[key][1]['b', False] = 1
	if len(NodeDict2[key][0]) == 1:
		TerminalNodes.append(key)

def MergeNodes(L1, L2, M):
	Out = {('r', False): 0, ('b', False): 0, ('r', True): 0, ('b', True): 0}
	for key1 in L1:
		for key2 in L2:
			if key1[0] == key2[0]:
				NewKey = (key1[0], True)
			elif key1[1]:
				NewKey = key2
			else:
				NewKey = None
			if NewKey != None:
				Out[NewKey] += L1[key1] * L2[key2] % M
	return Out
Breakout = False
while not Breakout:
	ActiveNode = TerminalNodes.pop()
	while True:
		NextNode = NodeDict2[ActiveNode][0][0]
		NodeDict2[NextNode][0].remove(ActiveNode)
		NodeDict2[ActiveNode][0].remove(NextNode)
		assert len(NodeDict2[ActiveNode][0]) == 0
		NodeDict2[NextNode][1] = MergeNodes(NodeDict2[ActiveNode][1], NodeDict2[NextNode][1], M)
		NodeDict2[ActiveNode][1] = None
		if len(NodeDict2[NextNode][0]) == 1:
			ActiveNode = NextNode
		else:
			if len(NodeDict2[NextNode][0]) == 0:
				Breakout = True
			break
Result = (NodeDict2[NextNode][1]['b', True] + NodeDict2[NextNode][1]['r', True]) % M
print(Result)


import sys

def count(tree):
	list = [i for i in range(len(tree)) if len(tree[i][1]) == 1]
	get = None
	while list:
		icurrent = list.pop()
		current = tree[icurrent]
		tree[icurrent] = None
		if current is not None and current[1]:
			inext = current[1][0]
			next = tree[inext]
			next[1].remove(icurrent)
			(n0, k0) = next[0]
			(n1, k1) = current[0]
			next[0] = (((n0 + k0) * (n1 + k1) + n0 * n1) // 2, k0 * n1 // 2)
			if len(next[1]) == 1:
				list.append(inext)
			elif not next[1]:
				get = next[0][0]
	return get
mod = 10 ** 9 + 7
n = int(input().strip())
tree = [[(0, 2), []] for _ in range(n)]
for a0 in range(n - 1):
	(u, v) = input().strip().split(' ')
	(u, v) = (int(u), int(v))
	u -= 1
	v -= 1
	tree[u][1].append(v)
	tree[v][1].append(u)
print(count(tree) % mod)


from collections import defaultdict, Counter, deque
n = int(input())
edges = defaultdict(set)
degree = Counter()
for _ in range(n - 1):
	(u, v) = map(int, input().split())
	edges[u].add(v)
	edges[v].add(u)
	degree[u] += 1
	degree[v] += 1
count = {u: {True: 1, False: 1} for u in degree}
leaves = deque([u for u in degree if degree[u] == 1])
while True:
	node = leaves.popleft()
	count[node][False] = count[node][True] - count[node][False]
	if not degree[node]:
		root = node
		break
	else:
		parent = edges[node].pop()
		edges[parent].discard(node)
		degree[parent] -= 1
		if degree[parent] == 1:
			leaves.append(parent)
		count[parent][True] *= count[node][True] + count[node][False]
		count[parent][False] *= count[node][False]
total = 2 * count[root][0]
print(total % (10 ** 9 + 7))


from collections import defaultdict, Counter, deque
n = int(input())
edges = defaultdict(set)
degree = Counter()
for _ in range(n - 1):
	(u, v) = map(int, input().split())
	edges[u].add(v)
	edges[v].add(u)
	degree[u] += 1
	degree[v] += 1
count = {u: {True: 1, False: 1} for u in degree}
leaves = deque([u for u in degree if degree[u] == 1])
while True:
	node = leaves.popleft()
	count[node][False] = count[node][True] - count[node][False]
	if not degree[node]:
		root = node
		break
	else:
		parent = edges[node].pop()
		edges[parent].discard(node)
		degree[parent] -= 1
		if degree[parent] == 1:
			leaves.append(parent)
		count[parent][True] *= count[node][True] + count[node][False]
		count[parent][False] *= count[node][False]
total = 2 * count[root][0]
print(total % (10 ** 9 + 7))


import math
import os
import random
import re
import sys
from collections import defaultdict, Counter, deque
n = int(input())
edges = defaultdict(set)
degree = Counter()
for _ in range(n - 1):
	(u, v) = map(int, input().split())
	edges[u].add(v)
	edges[v].add(u)
	degree[u] += 1
	degree[v] += 1
count = {u: {True: 1, False: 1} for u in degree}
leaves = deque([u for u in degree if degree[u] == 1])
while True:
	node = leaves.popleft()
	count[node][False] = count[node][True] - count[node][False]
	if not degree[node]:
		root = node
		break
	else:
		parent = edges[node].pop()
		edges[parent].discard(node)
		degree[parent] -= 1
		if degree[parent] == 1:
			leaves.append(parent)
		count[parent][True] *= count[node][True] + count[node][False]
		count[parent][False] *= count[node][False]
total = 2 * count[root][0]
print(total % (10 ** 9 + 7))


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

def dfs1(node):
	bool[node] = True
	for i in hash[node]:
		if bool[i] == False:
			par[i] = node
			dfs1(i)

def dfs2(node):
	bool[node] = True
	if len(hash[node]) == 1 and par[node] != node:
		B[node] = 1
		G[node] = 0
		return
	for i in hash[node]:
		if G[i] == -1 and bool[i] == False:
			dfs2(i)
	B[node] = 1
	G[node] = 1
	for i in hash[node]:
		if i != par[node]:
			B[node] *= G[i] % m
			G[node] *= (2 * G[i] % m + B[i] % m) % m
			B[node] = B[node] % m
			G[node] = G[node] % m
	G[node] -= B[node]
	while G[node] < 0:
		G[node] += m
from collections import defaultdict
n = int(input())
hash = defaultdict(list)
for i in range(n - 1):
	(a, b) = map(int, input().split())
	hash[a].append(b)
	hash[b].append(a)
bool = [False] * (n + 1)
par = [0] + [i + 1 for i in range(n)]
G = [-1] * (n + 1)
B = [-1] * (n + 1)
dfs1(1)
bool = [False] * (n + 1)
dfs2(1)
print(2 * G[1] % m)


import math
import os
import random
import re
import sys
from collections import defaultdict, Counter, deque
n = int(input())
edges = defaultdict(set)
degree = Counter()
for _ in range(n - 1):
	(u, v) = map(int, input().split())
	edges[u].add(v)
	edges[v].add(u)
	degree[u] += 1
	degree[v] += 1
count = {u: {True: 1, False: 1} for u in degree}
leaves = deque([u for u in degree if degree[u] == 1])
while True:
	node = leaves.popleft()
	count[node][False] = count[node][True] - count[node][False]
	if not degree[node]:
		root = node
		break
	else:
		parent = edges[node].pop()
		edges[parent].discard(node)
		degree[parent] -= 1
		if degree[parent] == 1:
			leaves.append(parent)
		count[parent][True] *= count[node][True] + count[node][False]
		count[parent][False] *= count[node][False]
total = 2 * count[root][0]
print(total % (10 ** 9 + 7))


from collections import defaultdict, Counter, deque
n = int(input())
edges = defaultdict(set)
degree = Counter()
for _ in range(n - 1):
	(u, v) = map(int, input().split())
	edges[u].add(v)
	edges[v].add(u)
	degree[u] += 1
	degree[v] += 1
count = {u: {True: 1, False: 1} for u in degree}
leaves = deque([u for u in degree if degree[u] == 1])
while True:
	node = leaves.popleft()
	count[node][False] = count[node][True] - count[node][False]
	if not degree[node]:
		root = node
		break
	else:
		parent = edges[node].pop()
		edges[parent].discard(node)
		degree[parent] -= 1
		if degree[parent] == 1:
			leaves.append(parent)
		count[parent][True] *= count[node][True] + count[node][False]
		count[parent][False] *= count[node][False]
total = 2 * count[root][0]
print(total % (10 ** 9 + 7))