Hongjun and the Tree 2

Time limit2sMemory limit512 MB

Summary

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

Level: Medium7 of 10
Topics: Tree, DFS, Dynamic programming, Combinatorics
Solved: No attempts yet

Problem

You are given a tree with $N$ vertices numbered from 0 to $N-1$ .

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

You can choose $k$ edges of the tree ( $0 \le k < N$ ) and delete them. The vertices then split into $k+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 $10^9+7$ .

Input

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

The second line contains $N-1$ integers $p_0, p_1, \dots, p_{N-2}$ ( $0 \le p_i \le i$ ). This means there is an edge between vertex $p_k$ and vertex $k+1$ .

The third line contains $N$ integers $x_0, x_1, \dots, x_{N-1}$ giving the color of each vertex. If $x_i$ is 0, vertex $i$ is white; if it is 1, vertex $i$ is black.

Output

Print the number of valid splittings modulo $10^9+7$ on one line.

Examples7

Example 1
Input
```
3
0 0 
0 1 1
```
Expected output
```
2
```
Example 2
Input
```
2
0
0 1
```
Expected output
```
1
```
Example 3
Input
```
3
0 0
1 1 0
```
Expected output
```
1
```
Example 4
Input
```
6
0 0 0 0 0
1 0 0 0 0 0
```
Expected output
```
1
```
Example 5
Input
```
6
0 0 0 0 0
0 1 1 1 1 1
```
Expected output
```
5
```
Example 6
Input
```
8
0 1 2 3 4 5 6
0 1 0 1 0 1 0 1
```
Expected output
```
8
```
Example 7
Input
```
7
0 1 0 3 0 5
1 0 1 0 1 0 1
```
Expected output
```
8
```