Appleman has a tree with n vertices. Some of the vertices (at least one) are colored black and other vertices are colored white.

Consider a set consisting of k (0 ≤ k < n) edges of Appleman's tree. If Appleman deletes these edges from the tree, then it will split into (k + 1) parts. Note, that each part will be a tree with colored vertices.

Now Appleman wonders, what is the number of sets splitting the tree in such a way that each resulting part will have exactly one black vertex? Find this number modulo 1000000007 (10^9 + 7).


-----Input-----

The first line contains an integer n (2  ≤ n ≤ 10^5) — the number of tree vertices. 

The second line contains the description of the tree: n - 1 integers p_0, p_1, ..., p_{n} - 2 (0 ≤ p_{i} ≤ i). Where p_{i} means that there is an edge connecting vertex (i + 1) of the tree and vertex p_{i}. Consider tree vertices are numbered from 0 to n - 1.

The third line contains the description of the colors of the vertices: n integers x_0, x_1, ..., x_{n} - 1 (x_{i} is either 0 or 1). If x_{i} is equal to 1, vertex i is colored black. Otherwise, vertex i is colored white.


-----Output-----

Output a single integer — the number of ways to split the tree modulo 1000000007 (10^9 + 7).


-----Examples-----
Input
3
0 0
0 1 1

Output
2

Input
6
0 1 1 0 4
1 1 0 0 1 0

Output
1

Input
10
0 1 2 1 4 4 4 0 8
0 0 0 1 0 1 1 0 0 1

Output
27

Difficulty: HARD
Tags: Tree algorithms

Dynamic programming

Graph traversal
Skill types: Dynamic programming

Starter code:

Solutions:
MOD = 1000000007
n = int(input())
p = [int(x) for x in input().split()]
x = [int(x) for x in input().split()]
children = [[] for x in range(n)]
for i in range(1, n):
	children[p[i - 1]].append(i)
count = [(0, 0) for i in range(n)]
for i in reversed(range(n)):
	prod = 1
	for ch in children[i]:
		prod *= count[ch][0] + count[ch][1]
	if x[i]:
		count[i] = (0, prod % MOD)
	else:
		tot = 0
		for ch in children[i]:
			cur = count[ch][1] * prod // (count[ch][0] + count[ch][1])
			tot += cur
		count[i] = (prod % MOD, tot % MOD)
print(count[0][1])


from collections import UserDict

class Tree(UserDict):

	def __init__(self, g):
		super().__init__()
		for (name, value) in enumerate(g, 1):
			self[value] = name

	def __setitem__(self, name, value):
		if name in self:
			if value is not None:
				self[name].add(value)
				self[value] = None
		elif value is None:
			super().__setitem__(name, set())
		else:
			super().__setitem__(name, {value})
			self[value] = None
n = int(input())
tree = Tree((int(i) for i in input().split()))
colors = [int(i) for i in input().split()]
t = [()] * n

def dfs(v):
	stack = [v]
	visited = set()
	while stack:
		v = stack.pop()
		if v not in visited:
			visited.add(v)
			stack.append(v)
			stack.extend(tree[v])
		else:
			t[v] = (1, colors[v])
			for u in tree[v]:
				t[v] = ((t[v][0] * t[u][1] + t[v][0] * t[u][0] * (not colors[u])) % (10 ** 9 + 7), (t[v][1] * t[u][1] + t[v][0] * t[u][1] * (not colors[v]) + t[v][1] * t[u][0] * (not colors[u])) % (10 ** 9 + 7))
dfs(0)
print(t[0][1])


MOD = 10 ** 9 + 7

def topo_compute(childrens, colors, parents):

	def f(node, connected_to_black):
		if colors[node] == 1 and connected_to_black:
			return 0
		children = childrens[node]
		if colors[node] == 1 or connected_to_black:
			ret = 1
			for child in children:
				x = dp_conn[child] + dp_not_conn[child]
				x %= MOD
				ret *= x
				ret %= MOD
			return ret
		s = 1
		prefix_prod = []
		for child in children:
			x = dp_conn[child] + dp_not_conn[child]
			x %= MOD
			s *= x
			s %= MOD
			prefix_prod.append(s)
		s = 1
		suffix_prod = []
		for child in reversed(children):
			x = dp_conn[child] + dp_not_conn[child]
			x %= MOD
			s *= x
			s %= MOD
			suffix_prod.append(s)
		suffix_prod = list(reversed(suffix_prod))
		ret = 0
		for i in range(len(children)):
			pre = prefix_prod[i - 1] if i > 0 else 1
			suf = suffix_prod[i + 1] if i + 1 < len(suffix_prod) else 1
			x = pre * suf
			x %= MOD
			x *= dp_not_conn[children[i]]
			x %= MOD
			ret += x
			ret %= MOD
		return ret
	num_childrens = [len(x) for x in childrens]
	N = len(childrens)
	dp_conn = [None] * N
	dp_not_conn = [None] * N
	stack = [i for i in range(N) if num_childrens[i] == 0]
	while True:
		node = stack.pop()
		dp_conn[node] = f(node, True)
		dp_not_conn[node] = f(node, False)
		parent = parents[node]
		if parent is None:
			return dp_not_conn[node]
		num_childrens[parent] -= 1
		if num_childrens[parent] == 0:
			stack.append(parent)

def build_tree(d, root):
	childrens = [None] * len(d)
	parents = [None] * len(d)
	stack = [(root, None)]
	while len(stack) > 0:
		(node, parent) = stack.pop()
		children = [x for x in d[node] if x != parent]
		childrens[node] = children
		parents[node] = parent
		for child in children:
			stack.append((child, node))
	return (childrens, parents)

def main():
	import sys
	n = sys.stdin.readline()
	n = int(n)
	p = map(int, sys.stdin.readline().split(' '))
	d = {}
	for i in range(n):
		d[i] = []
	for (i, b) in enumerate(p):
		a = i + 1
		d[a].append(b)
		d[b].append(a)
	colors = map(int, sys.stdin.readline().split(' '))
	colors = list(colors)
	for i in range(n - 1):
		line = sys.stdin.readline()
		if line == '':
			break
		(a, b) = map(int, line.split(' '))
		d[a].append(b)
		d[b].append(a)
	(childrens, parents) = build_tree(d, 0)
	ans = topo_compute(childrens, colors, parents)
	print(ans)
main()


n = int(input())
edges = [int(x) for x in input().split()]
color = [int(x) for x in input().split()]
graph = [[] for _ in range(n)]
for (a, b) in enumerate(edges):
	graph[a + 1].append(b)
	graph[b].append(a + 1)
dp = [[0] * 2 for _ in range(n)]
visited = [0] * n
stack = [0]
while stack:
	v = stack[-1]
	visited[v] = -1
	cn = 0
	for u in graph[v]:
		if visited[u] is not 0:
			continue
		else:
			cn += 1
			stack.append(u)
	if not cn:
		dp[v][0] = 1
		dp[v][1] = 0
		for u in graph[v]:
			if visited[u] is -1:
				continue
			dp[v][1] *= dp[u][0]
			dp[v][1] += dp[v][0] * dp[u][1]
			dp[v][0] *= dp[u][0]
			dp[v][1] %= 1000000007
			dp[v][0] %= 1000000007
		if color[v] is 1:
			dp[v][1] = dp[v][0]
		else:
			dp[v][0] += dp[v][1]
			dp[v][0] %= 1000000007
		visited[v] = 1
		stack.pop()
ans = dp[0][1]
print(ans)


mod = 10 ** 9 + 7
n = int(input())
edges = list(map(int, input().split()))
colored = list(map(int, input().split()))
childs = [[] for i in range(n)]
for i in range(1, n):
	childs[edges[i - 1]].append(i)
dp = [[0, 0] for i in range(n)]
for i in range(n - 1, -1, -1):
	prod = 1
	for child in childs[i]:
		prod *= sum(dp[child])
	if colored[i]:
		dp[i] = [0, prod % mod]
	else:
		sec = 0
		for child in childs[i]:
			now = dp[child][1] * prod // sum(dp[child])
			sec += now
		dp[i] = [prod % mod, sec % mod]
print(dp[0][1])


import os
import sys
from io import BytesIO, IOBase
from types import GeneratorType
from collections import defaultdict
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
sys.setrecursionlimit(2 * 10 ** 5)

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc

@bootstrap
def dfs(u):
	whites = 1
	k = []
	for j in adj[u]:
		res = (yield dfs(j))
		k.append(res)
		whites *= res[0] + res[1]
	black = 0
	for j in k:
		black += j[1] * (whites // (j[0] + j[1]))
	if color[u]:
		yield [0, whites % p]
	else:
		yield [whites % p, black % p]
p = 10 ** 9 + 7
n = int(input())
b = list(map(int, input().split()))
color = list(map(int, input().split()))
adj = [[] for i in range(n)]
for j in range(n - 1):
	adj[b[j]].append(j + 1)
print(dfs(0)[1])


import os, sys
from io import BytesIO, IOBase

def main():
	mod = 10 ** 9 + 7
	n = int(input())
	path = [[] for _ in range(n)]
	for (ind, i) in enumerate(map(int, input().split())):
		path[i].append(ind + 1)
		path[ind + 1].append(i)
	col = list(map(int, input().split()))
	dp = [[1, 0] for _ in range(n)]
	for i in range(n):
		dp[i][col[i]] = 1
		dp[i][col[i] ^ 1] = 0
	(st, poi, visi) = ([0], [0] * n, [1] + [0] * (n - 1))
	while len(st):
		(x, y) = (st[-1], path[st[-1]])
		if poi[x] != len(y) and visi[y[poi[x]]]:
			poi[x] += 1
		if poi[x] == len(y):
			if not col[st.pop()]:
				dp[x][1] = dp[x][1] * dp[x][0] % mod
			if len(st):
				if col[st[-1]]:
					dp[st[-1]][0] = 0
					dp[st[-1]][1] = dp[st[-1]][1] * sum(dp[x]) % mod
				else:
					dp[st[-1]][0] = dp[st[-1]][0] * sum(dp[x]) % mod
					dp[st[-1]][1] = (dp[st[-1]][1] + dp[x][1] * pow(sum(dp[x]), mod - 2, mod)) % mod
		else:
			i = y[poi[x]]
			st.append(i)
			visi[i] = 1
			poi[x] += 1
	print(dp[0][1])
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()