Problem Statement   You are given a tree T with n nodes.
The nodes are numbered 0 through n1.
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 n1 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 weight1 elements.    For each i, 0 <= p[i] <= i.    x will be between 1 and 1,000,000,000, inclusive.   Examples  0)     Returns: 1102110  The tree contains the edges 10 and 21, 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)     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.
