{"raw_statement":[{"iden":"background","content":"APJ：「？我家保险丝怎么又没了」\n"},{"iden":"statement","content":"给一棵 $n$ 个点的有根树，根是 $1$ 号结点。\n\n定义两个点集 $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$ 间的距离。\n\n定义 $\\operatorname{path}(u,v)$ 是 $u$ 到 $v$ 的简单路径上的所有点组成的集合，$\\mathcal L$ 是所有叶子组成的集合。\n\n对于固定正整数 $u$，定义满足如下条件的结点 $v$ 构成 $u$ 的半邻域 $\\mathring U(u)$：\n- $v$ 在 $u$ 子树内；\n- $\\operatorname{dist}(u,v)\\le\\operatorname{dist}(\\operatorname{path}(1,v),\\mathcal L)$。\n\n即 $u$ 的半邻域 $\\mathring U(u)$ 包含 $u$ 的子树内所有满足到 $u$ 的距离不大于它到根的路径上任意一点离最近叶子节点的距离的点。\n\n进而定义：\n$$f(x)=\\sum_{u\\in\\mathring U(x)}\\prod_{\\substack{v\\in\\operatorname{subtree}(u)\\\\v\\in\\mathring U(x)}}F_{\\deg v}$$\n其中 $\\operatorname{subtree}(u)$ 是 $u$ 子树中所有点组成的集合，$\\deg u$ 是 $u$ 的度数（与 $u$ 有连边的点的数量），$F$ 是 Fibonacci 数列：\n$$F_n=\\begin{cases}1&n\\le 2\\\\F_{n-1}+F_{n-2}&n\\ge 3\\end{cases}$$\n\n即 $f(x)$ 对应 $x$ 的半邻域中点对 $x$ 的贡献之和。而一个点 $u$ 对 $x$ 的贡献的计算方式为：取出每个 $u$ 子树内处在 $x$ 半邻域中的点 $v$，若 $v$ 的度数为 $d$，则将 $u$ 的贡献乘上 $F_d$，所有 $u$ 的贡献之和为结果。\n\n你需要求出 $f(1),f(2),\\cdots,f(n)$ 的值，为减少输出量，你只需要输出它们模 $994007158$ 后的异或和，即 $\\bigoplus_{x=1}^n(f(x)\\bmod 994007158)$ 即可。\n"},{"iden":"input","content":"第一行一个正整数 $n$ 表示点数。\n\n第二行 $n - 1$ 个正整数，第 $i$ 个正整数代表了结点 $i + 1$ 的父亲结点。"},{"iden":"output","content":"一行，表示 $\\bigoplus_{x=1}^n(f(x)\\bmod 994007158)$ 的值。"},{"iden":"note","content":"### 样例解释\n第一组数据中 $f$ 在 $1\\dots 7$ 处的取值：$8,2,2,1,1,1,1$。\n\n第二组数据中 $f$ 在 $1\\dots14$ 处的取值：$4,17,2,1,1,8,1,1,4,2,1,1,1,1$。\n### 数据范围\n\n**本题采用捆绑测试。**\n- Subtask 1 (10pts)：$n\\le 5000$。\n- Subtask 2 (20pts)：树的叶子个数不大于 $30$。\n- Subtask 3 (20pts)：树中没有恰有一个儿子的结点。\n- Subtask 4 (50pts)：无特殊限制。\n\n对于全部数据，$2\\le n,q\\le 10^6$，每个非根结点父亲的编号小于它的编号。\n"}],"translated_statement":null,"sample_group":[["7\n1 1 2 2 3 3\n","8"],["14\n1 2 3 3 2 6 6 6 9 9 10 11 12","25"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}