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 vector <int> weight with n elements.
You are also given a vector <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:vector <int>, vector <int>, int
Returns:int
Method signature:int count(vector <int> weight, vector <int> p, int x)


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 &lt= p[i] &lt= 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 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.