Problem Background

APJ: "Why is the fuse at my house gone again?"

UPD: The modulus has been updated ($998244353 \to 994007158$).

Problem Description

Given a rooted tree with $n$ nodes, where node 1 is the root.

Define the distance between two sets of points $S_1$ and $S_2$ as the minimum distance between any two points, one from each set, i.e., $\displaystyle\operatorname{dist}(S_1,S_2)=\min_{\substack{u\in S_1\\v\in S_2}}\operatorname{dist}(u,v)$, where $\operatorname{dist}(u,v)$ is the distance between points $u$ and $v$.

Define $\operatorname{path}(u,v)$ as the set of all points on the simple path from $u$ to $v$, and $\mathcal L$ as the set of all leaves.

For a fixed positive integer $u$, define the semi-neighborhood $\mathring U(u)$ of node $u$ as the set of nodes $v$ satisfying:
- $v$ is within the subtree of $u$;
- $\operatorname{dist}(u,v) \le \operatorname{dist}(\operatorname{path}(1,v), \mathcal L)$.

That is, the semi-neighborhood $\mathring U(u)$ includes all nodes within the subtree of $u$ whose distance to $u$ is not greater than the distance from any point on the path from the root to $v$ to the nearest leaf.

Further define:
$$f(x)=\sum_{u\in\mathring U(x)}\prod_{\substack{v\in\operatorname{subtree}(u)\\v\in\mathring U(x)}}F_{\deg v}$$
where $\operatorname{subtree}(u)$ is the set of all nodes in the subtree of $u$, $\deg u$ is the degree of $u$, and $F$ is the Fibonacci sequence:
$$F_n=\begin{cases}1&n\le 2\\F_{n-1}+F_{n-2}&n\ge 3\end{cases}$$

That is, $f(x)$ corresponds to the sum of contributions to $x$ from points in its semi-neighborhood. The contribution of a point $u$ to $x$ is calculated by taking each point $v$ in the subtree of $u$ that is also in the semi-neighborhood of $x$, and if $v$ has degree $d$, multiply the contribution of $u$ by $F_d$. The sum of all contributions from $u$ is the result.

You need to find the values of $f(1), f(2), \cdots, f(n)$, and to reduce the output size, you only need to output their XOR sum modulo $994007158$, i.e., $\bigoplus_{x=1}^n(f(x) \bmod 994007158)$.

Input Format

The first line contains a positive integer $n$ representing the number of nodes.

The second line contains $n - 1$ positive integers, where the $i$-th integer represents the parent node of node $i + 1$.

Output Format

One line, representing the value of $\bigoplus_{x=1}^n(f(x) \bmod 994007158)$.

Sample Input and Output

Input Sample #1

7
1 1 2 2 3 3

Output Sample #1

8

Input Sample #2

14
1 2 3 3 2 6 6 6 9 9 10 11 12

Output Sample #2

25

Notes/Hints

This problem uses bundled testing.
- Subtask 1 (10pts): $n \le 5000$.
- Subtask 2 (20pts): The number of leaves in the tree is no more than 30.
- Subtask 3 (20pts): There are no nodes with exactly one child in the tree.
- Subtask 4 (50pts): No special restrictions.

For all data, $2 \le n, q \le 10^6$, and the parent node of each non-root node has a smaller number than the node itself.

见题面 Input 部分

见题面 Output 部分