题目描述

有一棵包含 $N$ 个节点的有根树 $T$，节点分别编号为 $1, 2, \ldots, N$。节点 $1$ 是树 $T$ 的根节点，而节点 $i$ $(2 \le i \le N)$ 的（直接）父节点是 $P_i$。

此外，每个节点 $i$ $(1 \le i \le N)$ 拥有 $C_i$ 颗糖果。每一颗糖果都是不同的（可区分的）。

高桥给 $N$ 只松鼠下达了指令。具体来说，他向第 $i$ 只松鼠 $(1 \le i \le N)$ 下达如下指令：

• 在以节点 $i$ 为根的子树中，选择并收集 $D_i$ 颗糖果。

不同的松鼠不能拿走同一颗糖果。请输出所有松鼠选择糖果的可能方案数，对 $998244353$ 取模。

即使最终被选中的糖果集合完全相同，只要选择的松鼠不同，就会被视为不同的方案。

如果无法让所有松鼠按要求收集糖果，则输出 $0$。

输入格式

N
P_2 P_3 ... P_N
C_1 C_2 ... C_N
D_1 D_2 ... D_N

输出格式

输出方案数对 $998244353$ 取模的结果。

输入示例 1

5
1 1 3 3
1 2 1 2 3
1 1 3 1 1

输出示例 1

144

示例 1 说明

记节点 $1$ 拥有糖果 $1$，节点 $2$ 拥有糖果 $2,3$，节点 $3$ 拥有糖果 $4$，节点 $4$ 拥有糖果 $5,6$，节点 $5$ 拥有糖果 $7,8,9$。

其中一种合法方案：

• 松鼠 $1$ 从根节点子树（节点 $1,2,3,4,5$）中拿走糖果 $3$；
• 松鼠 $2$ 从节点 $2$ 子树（只含节点 $2$）中拿走糖果 $2$；
• 松鼠 $3$ 从节点 $3$ 子树（节点 $3,4,5$）中拿走糖果 $4,7,9$；
• 松鼠 $4$ 从节点 $4$ 子树（只含节点 $4$）中拿走糖果 $6$；
• 松鼠 $5$ 从节点 $5$ 子树（只含节点 $5$）中拿走糖果 $8$。

总共 $144$ 种合法方案，所以输出 $144$。

输入示例 2

2
1
1 1
2 1

输出示例 2

0

示例 2 说明

整棵树只有 $2$ 颗糖果，无法满足两只松鼠都按指令收集，所以输出 $0$。

输入示例 3

3
3 1
1000000000 1 1
1 1 1

输出示例 3

1755647

约束条件

• $2 \le N \le 2 \times 10^5$
• $1 \le P_i \le N$
• $1 \le C_i \le 10^9$
• $1 \le D_i$
• $D_1 + D_2 + \cdots + D_N \le 10^6$
• 所有输入值均为整数
• $T$ 是一棵以节点 $1$ 为根的有根树