题目描述

有一棵有 $N$ 个顶点的有根树，顶点编号为 $1$ 到 $N$。顶点 $1$ 是根，顶点 $i$（$2\leq i\leq N$）的父节点是 $P_i$。

给定一个非负整数 $r$ 和一个非负整数列 $A = (A_1, \ldots, A_N)$。你可以对这个数列进行任意次（也可以不进行）如下操作：

• 选择一个满足 $i \geq 2$ 且 $A_i \geq 1$ 的 $i$。将 $A_i$ 变为 $A_i - 1$，并将 $A_{P_i}$ 变为 $A_{P_i} + r$。

请你求出，最终可能得到的不同非负整数列 $A$ 的个数，答案对 $998244353$ 取模。

输入格式

输入以如下格式从标准输入给出。

$N$ $P_2$ $\ldots$ $P_N$ $r$ $A_1$ $\ldots$ $A_N$

输出格式

输出最终可能得到的不同非负整数列 $A$ 的个数，对 $998244353$ 取模。

样例 1

输入

3
1 1
2
1 1 1

输出

4

样例 2

输入

3
1 2
1
1 1 1

输出

5

样例 3

输入

3
1 2
2
1 1 1

输出

6

样例 4

输入

5
1 1 3 3
2
0 1 0 1 2

输出

48

样例 5

输入

5
1 1 3 3
123456789
1 2 3 4 5

输出

87782255

说明/提示

限制条件

• $2 \leq N \leq 300$
• $1 \leq P_i \leq i-1$（$2 \leq i \leq N$）
• $0 \leq r \leq 10^9$
• $0 \leq A_i \leq 10^9$

样例解释 1

最终可能得到的 $A$ 有以下 $4$ 种：$(1,1,1)$、$(3,0,1)$、$(3,1,0)$、$(5,0,0)$。

样例解释 2

最终可能得到的 $A$ 有以下 $5$ 种：$(1,1,1)$、$(1,2,0)$、$(2,0,1)$、$(2,1,0)$、$(3,0,0)$。

样例解释 3

最终可能得到的 $A$ 有以下 $6$ 种：$(1,1,1)$、$(1,3,0)$、$(3,0,1)$、$(3,2,0)$、$(5,1,0)$、$(7,0,0)$。

由 ChatGPT 4.1 翻译