홍준이와 트리 2

트리에서 간선을 잘라 모든 조각이 검은 정점을 정확히 하나씩 포함하도록 만드는 방법의 수를 세어 1e9+7로 나눈 나머지를 구한다.

보통7트리DFS동적 계획법조합론아직 제출이 없습니다시간 제한2초메모리 제한512 MB

문제

0번부터 N1N-1번까지 번호가 붙은 NN개의 정점으로 이루어진 트리가 주어진다.

각 정점은 흰색 또는 검은색으로 칠해져 있고, 두 색 모두 최소 한 개의 정점에 칠해져 있음이 보장된다.

이때 트리에서 간선 kk개(0k<N0 \le k < N)를 골라 없앨 수 있다. 그러면 정점 집합이 k+1k+1개로 나뉜다. 나뉜 집합이 모두 검은색 정점을 정확히 하나씩만 포함하도록 트리를 분할하는 경우의 수를 구하시오. 값이 매우 커질 수 있으므로 109+710^9+7로 나눈 나머지를 출력한다.

입력

첫째 줄에 정점의 개수 NN (1N1000001 \le N \le 100000)이 주어진다.

둘째 줄에 N1N-1개의 정수 p0,p1,,pN2p_0, p_1, \dots, p_{N-2} (0pii0 \le p_i \le i)가 주어진다. 정점 pkp_k와 정점 k+1k+1을 잇는 간선이 있다는 뜻이다.

셋째 줄에 각 정점의 색을 나타내는 NN개의 정수 x0,x1,,xN1x_0, x_1, \dots, x_{N-1}이 주어진다. xix_i가 0이면 ii번 정점이 흰색, 1이면 검은색이다.

출력

조건을 만족하는 분할의 경우의 수를 109+710^9+7로 나눈 나머지를 한 줄에 출력한다.