A9639 | Appleman and Tree

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

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 a single integer — the number of ways to split the tree modulo $1000000007$ ( $10^{9}+7$ ).