题目描述

给定一棵包含 $n$ 个结点的树 $T$、一个长度为 $n$ 的数列 $a$ 和一个整数 $p$，其中树 $T$ 的根结点为 $1$ 号结点，结点 $i$ 的权值为 $a_i$。

我们定义：

• $g(x)$ 为结点 $x$ 的父亲结点。特别地，$g(1)=1$。
• $d(x)$ 为结点 $x$ 到根结点之间的简单路径所包含的边的数量。特别地，$d(1)=0$。

我们继而定义：

$$f_k(x)=\begin{cases}x&k=0\\g(f_{k-1}(x))&k\ge 1\end{cases} $$

你需要求出 $ \sum\limits_{i=1}^{n}\sum\limits_{j=0}^{d(i)} \left( \binom{j+p }{j}\times a_{f_j(i)}\right)$ 的值。

由于答案可能很大，所以你只需要输出答案对 $m$ 取模的结果。

其中，$\binom{i}{j}$ 表示组合数，此处 $i$ 和 $j$ 为满足 $j \le i$ 的自然数，$\binom{i}{j}$ 的意义为从 $i$ 个不同的物品中选择 $j$ 个的方案数，例如 $\binom{3}{2}=3$，$\binom{5}{3}=10$，$\binom{4}{0}=1$，$\binom{3}{3}=1$。

输入格式

• 第一行输入三个整数 $n,p,m$。
• 第二行输入 $n$ 个整数，表示给定的数列 $a$。
• 第三行输入 $n-1$ 个整数，其中第 $i$ 个整数表示 $g(i+1)$ 的值。

输出格式

输出一行一个整数，表示答案。

输入输出样例 #1

输入 #1

5 7 124
11 4 13 12 14
1 2 2 2

输出 #1

62

输入输出样例 #2

输入 #2

4 0 180
8 8 14 8
1 1 3

输出 #2

76

输入输出样例 #3

输入 #3

3 5 105
15 8 8 
1 1 

输出 #3

1

说明/提示

【样例解释 #3】

对于第 $3$ 组数据，答案为 $\binom{5}{0}\times(15+8+8)+\binom{6}{1}\times(15+15)=211$，$211\bmod 105=1$。

【数据范围】

对于所有数据，$1 \le n \le 2 \times 10^4$，$0 \le p \le 10^3$，$1 \le a_i < m \le 10^9,1 \le g(i) \le i-1$。

本题采用捆绑测试计分。

Sub 编号	约束条件	分数
1	$n \le 1000$	$~15~$
2	保证树为菊花图，即 $g(i)=1$	$~15$
3	保证树为一条链，即 $g(i)=i-1$	$~20~$
4	$m=998244353$	$~20$
5	无特殊限制	$~30$

其中子任务 5 依赖子任务 1,2,3,4。