题目描述

给出一棵 $n$ 个节点的树，每个点有点权 $a_v$。定义一棵树的一个子连通块为一个树中点的非空集合，满足这些点在树上形成一个连通块。定义子连通块 $S$ 的权值为 $\prod_{v\in S}(a_v+|S|)$。求所有子连通块的权值之和对 $U^V$ 取模。

如果你认为自己做法的复杂度正确而被卡常，请尝试减少取模次数或优化无用转移。

输入格式

第一行，三个正整数 $n,U,V$，分别表示节点个数，以及模数（$U^V$）。

第二行，$n-1$ 个正整数 $f_2,f_3,\dots,f_n$，分别表示以 $1$ 节点为根节点的情况下第 $i$ 个点的父亲节点。

第三行，$n$ 个非负整数 $a_i$，表示每个点的点权。

输出格式

一行，一个正整数，表示所有子联通块的权值之和，对 $U^V$ 取模。

样例输入 1

3 10 6
1 1
1 2 3

样例输出 1

156

样例解释 1

对于样例 $1$，以下子连通块的权值分别是：

• $\{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$。

总和为 $2+3+4+12+15+120=156$，对 $10^6$ 取模后为 $156$。

样例输入 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

样例输出 2

678

样例 3~9

见附加文件。分别满足每个子任务的限制。

数据范围

对于所有数据满足 $1\leq n\leq2000$，$1\leq f_i<i$，$2\leq U\leq10$，$1\leq V\leq6$，$0\leq a_i\le 10^6$。