题目背景

APJ：「？我家保险丝怎么又没了」

题目描述

给一棵 $n$ 个点的有根树，根是 $1$ 号结点。

定义两个点集 $S_1,S_2$ 的距离为从两个集合分别选出一个点，能得到两点间距离的最小值，即 $\displaystyle\operatorname{dist}(S_1,S_2)=\min_{\substack{u\in S_1\\v\in S_2}}\operatorname{dist}(u,v)$，其中 $\operatorname{dist}(u,v)$ 是点 $u,v$ 间的距离。

定义 $\operatorname{path}(u,v)$ 是 $u$ 到 $v$ 的简单路径上的所有点组成的集合，$\mathcal L$ 是所有叶子组成的集合。

对于固定正整数 $u$，定义满足如下条件的结点 $v$ 构成 $u$ 的半邻域 $\mathring U(u)$：

• $v$ 在 $u$ 子树内；
• $\operatorname{dist}(u,v)\le\operatorname{dist}(\operatorname{path}(1,v),\mathcal L)$。

即 $u$ 的半邻域 $\mathring U(u)$ 包含 $u$ 的子树内所有满足到 $u$ 的距离不大于它到根的路径上任意一点离最近叶子节点的距离的点。

进而定义：

其中 $\operatorname{subtree}(u)$ 是 $u$ 子树中所有点组成的集合，$\deg u$ 是 $u$ 的度数（与 $u$ 有连边的点的数量），$F$ 是 Fibonacci 数列：

即 $f(x)$ 对应 $x$ 的半邻域中点对 $x$ 的贡献之和。而一个点 $u$ 对 $x$ 的贡献的计算方式为：取出每个 $u$ 子树内处在 $x$ 半邻域中的点 $v$，若 $v$ 的度数为 $d$，则将 $u$ 的贡献乘上 $F_d$，所有 $u$ 的贡献之和为结果。

你需要求出 $f(1),f(2),\cdots,f(n)$ 的值，为减少输出量，你只需要输出它们模 $994007158$ 后的异或和，即 $\bigoplus_{x=1}^n(f(x)\bmod 994007158)$ 即可。

输入格式

第一行一个正整数 $n$ 表示点数。

第二行 $n - 1$ 个正整数，第 $i$ 个正整数代表了结点 $i + 1$ 的父亲结点。

输出格式

一行，表示 $\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

提示

样例解释

第一组数据中 $f$ 在 $1\dots 7$ 处的取值：$8,2,2,1,1,1,1$。

第二组数据中 $f$ 在 $1\dots14$ 处的取值：$4,17,2,1,1,8,1,1,4,2,1,1,1,1$。

数据范围

本题采用捆绑测试。

• Subtask 1 (10pts)：$n\le 5000$。
• Subtask 2 (20pts)：树的叶子个数不大于 $30$。
• Subtask 3 (20pts)：树中没有恰有一个儿子的结点。
• Subtask 4 (50pts)：无特殊限制。

对于全部数据，$2\le n,q\le 10^6$，每个非根结点父亲的编号小于它的编号。