ADAGRAFT - Ada and Graft

no tags 

As you might already know, Ada the Ladybug is a farmer. She grows a big fruit tree (with root in 0). There is a fruit on every node of the tree. Ada is competing in grafting competition and this is her masterpiece. The most valuable tree wins the competition. The value of tree is product of values of each node. The value of a node is the sum of distinct fruit kinds in its subtree.

Can you find the value of Ada's tree? Since this number might be pretty big, output it modulo 109+7

Input

The first and line will contain 1 ≤ N ≤ 4*105.

The next line will contain N-1 integers 0 ≤ pi < i, the parent of ith node.

The next line will contain N integers 0 ≤ Fi ≤ 109, the fruit growing on ith node.

Output

Print a single integer - the value of tree modulo 1000000007.

Example Input

5
0 0 1 1
1 1 1 2 2

Example Output

4

Example Input

4
0 1 2
6 7 2 3

Example Output

24

Example Input

11
0 1 1 1 3 5 2 7 5 4
494052753 959648710 959648710 959648710 494052753 959648710 959648710 959648710 959648710 494052753 959648710

Example Output

32

hide comments
julkas: 2017-11-18 16:40:58

@anpans Hi, Anastasis! What is your approach for this problem?

julkas: 2017-11-12 13:41:34

Good problem. See also - https://www.hackerrank.com/contests/101feb14/challenges/coloring-tree


Added by:Morass
Date:2017-11-06
Time limit:3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All