human
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
Solve the task in PYTHON3.

What is a Python program to find this number modulo 1000000007 (109 + 7)?
assistant
#Here is Python program to find this number modulo 1000000007 (109 + 7).

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...