Hongjun and the Tree 2

Count the ways to cut edges of a tree so every remaining component has exactly one black vertex, modulo 1e9+7.

Medium7TreeDFSDynamic programmingCombinatoricsNo attempts yetTime limit2sMemory limit512 MB

Problem

You are given a tree with NN vertices numbered from 0 to N1N-1.

Each vertex is painted white or black, and at least one vertex of each color is guaranteed to exist.

You can choose kk edges of the tree (0k<N0 \le k < N) and delete them. The vertices then split into k+1k+1 sets. Count the ways to split the tree so that every resulting set contains exactly one black vertex. The value can grow very large, so print it modulo 109+710^9+7.

Input

The first line contains the number of vertices NN (1N1000001 \le N \le 100000).

The second line contains N1N-1 integers p0,p1,,pN2p_0, p_1, \dots, p_{N-2} (0pii0 \le p_i \le i). This means there is an edge between vertex pkp_k and vertex k+1k+1.

The third line contains NN integers x0,x1,,xN1x_0, x_1, \dots, x_{N-1} giving the color of each vertex. If xix_i is 0, vertex ii is white; if it is 1, vertex ii is black.

Output

Print the number of valid splittings modulo 109+710^9+7 on one line.