P10175 "OICon-02" Subtree Value

Given a tree with $n$ nodes, each node has a weight $a_v$. Define a connected subgraph of a tree as a **non-empty set** of nodes in the tree such that these nodes form a connected block in the tree. Define the value of a connected subgraph $S$ as $\prod_{v\in S}(a_v+|S|)$. Compute the sum of the values of all connected subgraphs, modulo $U^V$.

The first line contains three positive integers $n, U, V$, representing the number of nodes and the modulus ($U^V$). The second line contains $n-1$ positive integers $f_2, f_3, \dots, f_n$, where $f_i$ is the parent of node $i$ when the tree is rooted at node $1$. The third line contains $n$ non-negative integers $a_i$, representing the weight of each node.

One line containing one positive integer, representing the sum of the values of all connected subgraphs, modulo $U^V$.

### Sample Explanation For sample $1$, the values of the following connected subgraphs are: * $\{1\}$: $(1+1)=2$; * $\{2\}$: $(2+1)=3$; * $\{3\}$: $(3+1)=4$; * $\{1,2\}$: $(1+2)\times(2+2)=12$; * $\{1,3\}$: $(1+2)\times(3+2)=15$; * $\{1,2,3\}$: $(1+3)\times(2+3)\times(3+3)=120$. The total sum is $2+3+4+12+15+120=156$, and after taking modulo $10^6$ it is $156$. ### Constraints **This problem uses bundled testdata.** | $\text{Subtask}$ | Special Property | $\text{Score}$ | |:--:|:--:|:--:| | $1$ | $n\leq10$ | $5$ | | $2$ | $n\leq150$ | $8$ | | $3$ | $n\leq500$ | $11$ | | $4$ | $U=2,V=1$ | $7$ | | $5$ | $V=1$ | $23$ | | $6$ | $U\mid a_i$ | $23$ | | $7$ | No special limits | $23$ | For $100\%$ of the data: $1\leq n\leq2000$, $1\leq f_i