Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

B. Appleman and Tree

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputAppleman 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).

Input

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

Output a single integer — the number of ways to split the tree modulo 1000000007 (10^{9} + 7).

Examples

Input

3

0 0

0 1 1

Output

2

Input

6

0 1 1 0 4

1 1 0 0 1 0

Output

1

Input

10

0 1 2 1 4 4 4 0 8

0 0 0 1 0 1 1 0 0 1

Output

27

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/15/2018 06:39:58 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|