Problem Description

Given a tree with $n$ nodes, the $i$-th node has a node weight $x_i$.

For the $n-1$ edges on the tree, each edge can be chosen to be deleted or kept, so there are $2^{n-1}$ ways to decide whether to delete each edge.

For each edge-deletion plan, suppose the resulting graph has $k$ connected components. Define the value of this plan as the product of the XOR sums of node weights within each connected component. Formally, if the graph contains connected components $C_1,C_2,\ldots,C_k$, where $C_i$ is the vertex set of the $i$-th connected component, let $v_i=\bigoplus_{u\in C_i} x_u$, then the value of this plan is $v_1\times v_2\times \cdots\times v_k$.

Find the sum of the values over all these $2^{n-1}$ edge-deletion plans, and output the answer modulo $998~244~353$.

Input Format

Read input from standard input.

The first line contains a positive integer $n$, denoting the number of nodes in the tree.

The second line contains $n$ non-negative integers $x_1,x_2,\ldots,x_n$, denoting the node weight of each node.

The third line contains $n-1$ positive integers $f_2,f_3,\ldots,f_n$, indicating that there is an undirected edge between node $i$ and $f_{i}$.

Output Format

Write output to standard output.

Output one line containing one integer, denoting the sum of the values over all $2^{n-1}$ edge-deletion plans, modulo $998~244~353$.

3
1 2 3
1 1

19

5
3 4 5 6 7
1 1 2 2

5985

Hint

[Sample Explanation #1]

There are four edge-deletion plans:

• Delete no edges: the graph has exactly one connected component, and the value is $1\oplus2\oplus3=0$.
• Delete edge $(1,2)$: the graph has two connected components, and the value is $(1\oplus3)\times2=4$.
• Delete edge $(1,3)$: the graph has two connected components, and the value is $(1\oplus2)\times3=9$.
• Delete edges $(1,2)$ and $(1,3)$: the graph has three connected components, and the value is $1\times2\times3=6$.

The total sum of values is $0+4+9+6=19$.

[Sample #3]

See xor/xor3.in and xor/xor3.ans in the contestant directory.

This sample satisfies the constraints for test points $6\sim7$.

[Sample #4]

See xor/xor4.in and xor/xor4.ans in the contestant directory.

This sample satisfies the constraints for test point $8$.

[Sample #5]

See xor/xor5.in and xor/xor5.ans in the contestant directory.

This sample satisfies the constraints for test point $9$.

[Sample #6]

See xor/xor6.in and xor/xor6.ans in the contestant directory.

This sample satisfies the constraints for test points $19\sim21$.

[Constraints]

For all data, it is guaranteed that: $1\leq n\leq5\times10^5$, $0\leq x_i\leq10^{18}$, $1\leq f_i<i$.

• Special Property A: it is guaranteed that for any $1< i\le n$, $f_i=i-1$.
• Special Property B: it is guaranteed that for any $1< i\le n$, $f_i=1$.

[Notes]

$\oplus$ denotes the bitwise XOR operation.

The input and output size of this problem is large, so please use appropriate I/O methods.

Please pay attention to the impact of constant factors on the program’s running time.

Translated by ChatGPT 5