Semi‐Neighborhood Tree Function

You are given a rooted tree with n nodes, with node 1 as the root. Consider the following definitions.

For any two sets of nodes \(S_1\) and \(S_2\), define their distance as \[ \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\).

For any two nodes \(u,v\), let \(\operatorname{path}(u,v)\) denote the set of nodes on the unique simple path from \(u\) to \(v\). Let \(\mathcal{L}\) be the set of all leaves (i.e. nodes with no children).

For a fixed node \(x\) (acting as the reference), define the semi‐neighborhood of a node \(u\) (with \(u\) in the tree) as follows: a node \(v\) belongs to \(\mathring U(u)\) if and only if

• \(v\) is in the subtree of \(u\), and
• \(\operatorname{dist}(u,v)\le \operatorname{dist}(\operatorname{path}(1,v),\mathcal{L})\).

The value \(f(x)\) is then defined for every node \(x\) by \[ 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 nodes in the subtree of \(u\) (with respect to the rooted tree),
• \(\deg v\) is the degree of node \(v\) in the tree (i.e. the number of nodes adjacent to \(v\); note that for non-root nodes, this equals the number of children plus one), and
• The Fibonacci numbers \(F_n\) are defined in \(\LaTeX\) by \[ F_n=\begin{cases}1,&n\le 2\\ F_{n-1}+F_{n-2},&n\ge 3\end{cases}. \]

In other words, for a fixed node \(x\), let \[ S(x)=\{v\text{ in the subtree of }x : \operatorname{dist}(x,v)\le \min_{w\in \operatorname{path}(1,v)}\operatorname{dist}(w,\mathcal{L})\}. \] Then for every \(u\in S(x)\), define its contribution as \[ G(u)=\prod_{v\in \operatorname{subtree}(u)\cap S(x)} F_{\deg v}, \] and \[ f(x)=\sum_{u\in S(x)} G(u). \]

Your task is to compute \(f(1),f(2),\dots,f(n)\) and output the bitwise XOR of their remainders modulo M, where \[ M=994007158\quad\text{and}\quad \text{Answer}=\bigoplus_{x=1}^n \Bigl(f(x)\bmod M\Bigr). \]

Note: It is guaranteed that if a node fails the condition \(\operatorname{dist}(x,v)\le \min_{w\in\operatorname{path}(1,v)}\operatorname{dist}(w,\mathcal{L})\), then all of its descendants also fail the condition.

inputFormat

The first line contains an integer n (number of nodes).

If n > 1, the second line contains n-1 integers. The i-th integer (for i = 1,2,...,n-1) represents the parent of node i+1 in the tree.

outputFormat

Output a single integer, the XOR over f(x) mod 994007158 for every node x from 1 to n.

sample

1

1

</p>