Problem Description

Given a tree with $n$ nodes, each node has a weight $a_v$. Define a subtree as a non-empty subset of nodes in the tree such that these nodes form a connected component. The value of a subtree $S$ is defined as $\prod_{v\in S}(a_v+|S|)$. Calculate the sum of the values of all subtrees 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$, representing the parent node of the $i$-th node when the tree is rooted at node $1$.

The third line contains $n$ non-negative integers $a_i$, representing the weights of each node.

Output Format

A single line containing a positive integer, representing the sum of the values of all subtrees modulo $U^V$.

Sample Input and Output

Input Sample #1

3 10 6
1 1
1 2 3

Output Sample #1

156

Input Sample #2

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

Output Sample #2

678

Notes/Hints

Sample Explanation

For Sample $1$, the values of the following subtrees 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$, which modulo $10^6$ is $156$.

Data Range

This problem uses subtask testing.

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

见题面 Input 部分

见题面 Output 部分