Problem Description

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$.

Input Format

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.

Output Format

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

3 10 6
1 1
1 2 3

156

11 4 6
1 1 2 3 4 4 4 5 6 7
325 190 400 325 380 165 334 400 80 171 340

678

Hint

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.

For $100\%$ of the data: $1\leq n\leq2000$, $1\leq f_i<i$, $2\leq U\leq10$, $1\leq V\leq6$, $0\leq a_i< U^V$.

Translated by ChatGPT 5