462_D. Appleman and Tree_17195
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 (109 + 7).

Input

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

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

The third line contains the description of the colors of the vertices: n integers x0, x1, ..., xn - 1 (xi is either 0 or 1). If xi 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 (109 + 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
#!/usr/bin/python

#
# Codeforces
# 426/D non-recursive; 
#
# @author godmar@gmail.com
#
from collections import defaultdict
from operator import mul

def InputInts(): return map(int, raw_input().split())

def productof(L):
    return reduce(mul, L, 1)

n = InputInts()[0]
P = InputInts()     # parents
colorof = InputInts()     # colors

BLACK=1
WHITE=0

# compute lists of children for each node
children = defaultdict(list)
for i, p in enumerate(P):
    children[p].append(i+1)

# post-order traversal
# returns pair (b, w) where b counts the number of
# ways to split the subtree such that the node is part
# of a component that contains a black node
# w counts the number of ways such that it does not.
def traverse(vertex):
    dfsstack = [0]
    results = []

    def reducenode(vertex, chresults):
        # summarize
        bwprod = productof((b+w for b, w in chresults if b > 0))

        if colorof[vertex] == BLACK:
            b = bwprod
            w = 0
        else:
            b = sum(_b * bwprod/(_b+_w) for _b, _w in chresults if _b > 0 and _b + _w > 0)
            w = bwprod

        return b, w

    while len(dfsstack) > 0:
        vertex = dfsstack.pop()

        #print "visiting ", vertex, "stack is", dfsstack
        for child in children[vertex]:
            dfsstack.append(child)

        if len(children[vertex]) == 0:
            results.append((1, 0) if colorof[vertex] == BLACK else (0, 1))

            #print "reached leaf: ", vertex, P[vertex-1]
            stopAt = P[dfsstack[-1]-1] if len(dfsstack) > 0 else -1
            #print "stop At", stopAt
            while vertex != 0 and P[vertex-1] != stopAt:
                vertex = P[vertex-1]
                #print "reducing", vertex
                chresults = results[-len(children[vertex]):]
                del results[-len(children[vertex]):]
                results.append(reducenode(vertex, chresults))
        else:
            pass

    return results[0]

b, w = traverse(0)
print b % (10**9 + 7)
