트리에서 간선을 잘라 모든 조각이 검은 정점을 정확히 하나씩 포함하도록 만드는 방법의 수를 세어 1e9+7로 나눈 나머지를 구한다.
0번부터 N−1N-1N−1번까지 번호가 붙은 NNN개의 정점으로 이루어진 트리가 주어진다.
각 정점은 흰색 또는 검은색으로 칠해져 있고, 두 색 모두 최소 한 개의 정점에 칠해져 있음이 보장된다.
이때 트리에서 간선 kkk개(0≤k<N0 \le k < N0≤k<N)를 골라 없앨 수 있다. 그러면 정점 집합이 k+1k+1k+1개로 나뉜다. 나뉜 집합이 모두 검은색 정점을 정확히 하나씩만 포함하도록 트리를 분할하는 경우의 수를 구하시오. 값이 매우 커질 수 있으므로 109+710^9+7109+7로 나눈 나머지를 출력한다.
첫째 줄에 정점의 개수 NNN (1≤N≤1000001 \le N \le 1000001≤N≤100000)이 주어진다.
둘째 줄에 N−1N-1N−1개의 정수 p0,p1,…,pN−2p_0, p_1, \dots, p_{N-2}p0,p1,…,pN−2 (0≤pi≤i0 \le p_i \le i0≤pi≤i)가 주어진다. 정점 pkp_kpk와 정점 k+1k+1k+1을 잇는 간선이 있다는 뜻이다.
셋째 줄에 각 정점의 색을 나타내는 NNN개의 정수 x0,x1,…,xN−1x_0, x_1, \dots, x_{N-1}x0,x1,…,xN−1이 주어진다. xix_ixi가 0이면 iii번 정점이 흰색, 1이면 검은색이다.
조건을 만족하는 분할의 경우의 수를 109+710^9+7109+7로 나눈 나머지를 한 줄에 출력한다.