Background

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

Problem Description

You are given a rooted tree with $n$ nodes, where the root is node $1$.

Define the distance between two node sets $S_1, S_2$ as the minimum distance between a node chosen 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 nodes $u$ and $v$.

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

For a fixed positive integer $u$, define the set of nodes $v$ that satisfy the following conditions to be the semi-neighborhood of $u$, denoted by $\mathring U(u)$:

• $v$ is in 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)$ contains all nodes $v$ in the subtree of $u$ such that the distance from $v$ to $u$ is no more than the distance from any node on the path from $v$ to the root to its nearest leaf node.

Then 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$ (the number of nodes adjacent to $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}$$

In other words, $f(x)$ is the sum of contributions of nodes in the semi-neighborhood of $x$. The contribution of a node $u$ to $x$ is computed as follows: take every node $v$ in the subtree of $u$ that is also in the semi-neighborhood of $x$; if the degree of $v$ is $d$, then multiply the contribution of $u$ by $F_d$. The final result is the sum of contributions of all such $u$.

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

Input Format

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

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

Output Format

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

7
1 1 2 2 3 3

8

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

25

Hint

Sample Explanation

In the first sample, the values of $f$ at $1\dots 7$ are: $8,2,2,1,1,1,1$.

In the second sample, the values of $f$ at $1\dots14$ are: $4,17,2,1,1,8,1,1,4,2,1,1,1,1$.

Constraints

This problem uses bundled testdata.

• Subtask 1 (10 pts): $n\le 5000$.
• Subtask 2 (20 pts): the number of leaves in the tree is at most $30$.
• Subtask 3 (20 pts): there is no node in the tree that has exactly one child.
• Subtask 4 (50 pts): no special restrictions.

For all testdata, $2\le n,q\le 10^6$, and for each non-root node, its parent index is smaller than its own index.

Translated by ChatGPT 5