JOIN

 Problem Statement

Problem Statement for SubtreeSumHash

### Problem Statement

You are given a tree T with n nodes. The nodes are numbered 0 through n-1. Each node of the tree has a positive integer weight. You are given the weights in the int[] weight with n elements. You are also given a int[] p with n-1 elements that describes the edges of the tree: for each valid i, there is an undirected edge between nodes (i+1) and p[i]. The constraints ensure that this will produce a valid tree.

A subtree of T is any subgraph of T that is a tree. The weight of a subtree is the sum of the weights of its vertices. Let S be the multiset that contains the weights of all nonempty subtrees of T. (In other words, for each subtree of T we calculate its total weight and add the result to S. Note that S may contain some duplicates.)

You are also given an int x. This value is used to define the hash of the multiset S: Hash(S) is defined as the sum of x^s over all elements s of S. For example, if S = {2, 3, 3} then Hash(S) = x^2 + x^3 + x^3.

Please calculate and return the value Hash(S) modulo 1,000,000,007.

### Definition

 Class: SubtreeSumHash Method: count Parameters: int[], int[], int Returns: int Method signature: int count(int[] weight, int[] p, int x) (be sure your method is public)

### Constraints

-weight will contain between 1 and 50 elements, inclusive.
-Each element in weight will be between 1 and 1,000,000,000, inclusive.
-p will contain exactly |weight|-1 elements.
-For each i, 0 <= p[i] <= i.
-x will be between 1 and 1,000,000,000, inclusive.

### Examples

0)

 `{1,2,3}` `{0,1}` `10`
`Returns: 1102110`
 The tree contains the edges 1-0 and 2-1, so it looks like this: 0 - 1 - 2. This tree has 6 subtrees: {0}, {1}, {2}, {0,1}, {1,2}, and {0,1,2}. Their weights are 1, 2, 3, 3, 5, and 6, respectively. Hence, S = {1, 2, 3, 3, 5, 6} and Hash(S) = x^1 + x^2 + 2*x^3 + x^5 + x^6 = 10 + 100 + 2*1000 + 100000 + 1000000 = 1102110.
1)

 `{123456789,987654321,111111111,999999999}` `{0,0,0}` `1`
`Returns: 11`
 There are 11 subtrees. Their weights do not matter: as x = 1, Hash(S) is simply the number of subtrees.
2)

 `{10}` `{}` `10`
`Returns: 999999937`
 The answer is 10^10 % (10^9+7).
3)

 `{3,7,6,8,9,4,2,1,5,6,7,8,9,6,1,2,3,5}` `{0,0,0,3,1,1,2,0,0,3,7,8,9,0,0,4,1}` `987654321`
`Returns: 46327623`

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
2017 TCO Algorithm Round 1B - Division I, Level Three