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: competition

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)

#print(children)

count = [(0,0) for i in range(n)]
for i in reversed(list(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
        else:
            if value is None:
                super().__setitem__(name, set())
            else:
                super().__setitem__(name, {value})
                self[value] = None


def __starting_point():
    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])



    




# Made By Mostafa_Khaled

__starting_point()

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 = list(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 = list(map(int, sys.stdin.readline().split(" ")))
    colors = list(colors)

    for i in range(n - 1):
        line = sys.stdin.readline()
        if line == "":
            break

        a, b = list(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)


def __starting_point():
    main()

__starting_point()