题目描述

给定一棵包含 $n$ 个节点的树，第 $i$ 个点有一个点权 $x_i$。

对于树上的 $n-1$ 条边，每条边选择删除或不删除，有 $2^{n-1}$ 种选择是否删除每条边的方案。

对于每种删除边的方案，设删除后的图包含 $k$ 个连通块，定义这个方案的权值为图中连通块点权异或和的乘积。形式化地说，若这张图包含连通块 $C_1,C_2,\ldots,C_k$，其中 $C_i$ 是第 $i$ 个连通块的顶点集合，设 $v_i=\bigoplus_{u\in C_i} x_u$，则这个方案的权值为 $v_1\times v_2\times \cdots\times v_k$。

求这 $2^{n-1}$ 种删除边的方案的权值之和，答案对 $998~244~353$ 取模。

输入格式

从标准输入读入数据。

输入的第一行包含一个正整数 $n$，表示树的节点个数。

第二行 $n$ 个非负整数 $x_1,x_2,\ldots,x_n$，表示每个点的点权。

第三行 $n-1$ 个正整数 $f_2,f_3,\ldots,f_n$，表示节点 $i$ 与 $f_{i}$ 之间有一条无向边。

输出格式

输出到标准输出。

输出包含一行一个整数，表示所有 $2^{n-1}$ 种删除边的方案的权值之和，答案对 $998~244~353$ 取模。

3
1 2 3
1 1

19

5
3 4 5 6 7
1 1 2 2

5985

提示

【样例解释 #1】

有四种删除边的方案：

• 不删除边：图有且仅有一个连通块，权值为 $1\oplus2\oplus3=0$。
• 删除 $(1,2)$ 一条边：图包含两个连通块，权值为 $(1\oplus3)\times2=4$。
• 删除 $(1,3)$ 一条边：图包含两个连通块，权值为 $(1\oplus2)\times3=9$。
• 删除 $(1,2)$，$(1,3)$ 两条边：图包含三个连通块，权值为 $1\times2\times3=6$。

所有方案权值的总和为 $0+4+9+6=19$。

【样例 #3】

见选手目录下的 xor/xor3.in 与 xor/xor3.ans。

这个样例满足测试点 $6\sim7$ 的条件限制。

【样例 #4】

见选手目录下的 xor/xor4.in 与 xor/xor4.ans。

这个样例满足测试点 $8$ 的条件限制。

【样例 #5】

见选手目录下的 xor/xor5.in 与 xor/xor5.ans。

这个样例满足测试点 $9$ 的条件限制。

【样例 #6】

见选手目录下的 xor/xor6.in 与 xor/xor6.ans。

这个样例满足测试点 $19\sim21$ 的条件限制。

---

【数据范围】

对于所有数据保证：$1\leq n\leq5\times10^5$，$0\leq x_i\leq10^{18}$，$1\leq f_i<i$。

测试点编号	$n\leq$	$x_i$	特殊性质
$1\sim2$	$12$	$\leq10^9$	无
$3$	$2000$	$=1$
$4$	$10^5$		A
$5$			B
$6\sim7$			无
$8$		$\leq7$	A
$9$			B
$10\sim11$			无
$12\sim16$	$200$	$\leq8191$
$17$	$10^5$	$\leq10^9$	A
$18$			B
$19\sim21$			无
$22\sim25$	$5\times10^5$	$\leq10^{18}$

• 特殊性质 A：保证对于任意 $1< i\le n$，$f_i=i-1$。
• 特殊性质 B：保证对于任意 $1< i\le n$，$f_i=1$。

---

【提示】

$\oplus$ 表示按位异或运算。

本题输入输出量较大，请使用适当的 I/O 方式。

请注意常数因子对程序运行效率产生的影响。