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

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'MOD = 10**9 + 7\n\n\ndef topo_compute(childrens, colors, parents):\n    def f(node, connected_to_black):\n        if colors[node] == 1 and connected_to_black:\n            return 0\n\n        children = childrens[node]\n        if colors[node] == 1 or connected_to_black:\n            ret = 1\n\n            for child in children:\n                x = dp_conn[child] + dp_not_conn[child]\n                x %= MOD\n\n                ret *= x\n                ret %= MOD\n\n            return ret\n\n        s = 1\n        prefix_prod = []\n        for child in children:\n            x = dp_conn[child] + dp_not_conn[child]\n            x %= MOD\n            s *= x\n            s %= MOD\n            prefix_prod.append(s)\n\n        s = 1\n        suffix_prod = []\n        for child in reversed(children):\n            x = dp_conn[child] + dp_not_conn[child]\n            x %= MOD\n            s *= x\n            s %= MOD\n            suffix_prod.append(s)\n\n        suffix_prod = list(reversed(suffix_prod))\n\n        ret = 0\n\n        for i in range(len(children)):\n            pre = prefix_prod[i - 1] if i > 0 else 1\n            suf = suffix_prod[i + 1] if i + 1 < len(suffix_prod) else 1\n\n            x = pre * suf\n            x %= MOD\n\n            x *= dp_not_conn[children[i]]\n            x %= MOD\n\n            ret += x\n            ret %= MOD\n\n        return ret\n\n    ########################\n\n    num_childrens = [len(x) for x in childrens]\n    N = len(childrens)\n    dp_conn = [None] * N\n    dp_not_conn = [None] * N\n\n    stack = [i for i in range(N) if num_childrens[i] == 0]\n\n    while True:\n        node = stack.pop()\n\n        dp_conn[node] = f(node, True)\n        dp_not_conn[node] = f(node, False)\n\n        parent = parents[node]\n\n        if parent is None:\n            return dp_not_conn[node]\n\n        num_childrens[parent] -= 1\n        if num_childrens[parent] == 0:\n            stack.append(parent)\n\n\ndef build_tree(d, root):\n    childrens = [None] * len(d)\n    parents = [None] * len(d)\n\n    stack = [(root, None)]\n\n    while len(stack) > 0:\n        node, parent = stack.pop()\n\n        children = [x for x in d[node] if x != parent]\n\n        childrens[node] = children\n        parents[node] = parent\n\n        for child in children:\n            stack.append((child, node))\n\n    return childrens, parents\n\n\ndef main():\n    import sys\n\n    n = sys.stdin.readline()\n    n = int(n)\n\n    p = list(map(int, sys.stdin.readline().split(" ")))\n\n    d = {}\n\n    for i in range(n):\n        d[i] = []\n\n    for i, b in enumerate(p):\n        a = i + 1\n        d[a].append(b)\n        d[b].append(a)\n\n    colors = list(map(int, sys.stdin.readline().split(" ")))\n    colors = list(colors)\n\n    for i in range(n - 1):\n        line = sys.stdin.readline()\n        if line == "":\n            break\n\n        a, b = list(map(int, line.split(" ")))\n\n        d[a].append(b)\n        d[b].append(a)\n\n    childrens, parents = build_tree(d, 0)\n\n    ans = topo_compute(childrens, colors, parents)\n    print(ans)\n\n\ndef __starting_point():\n    main()\n\n__starting_point()'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 15951