分数: 1000 点
问题陈述
Snuke有一棵有根树 N+1 顶点。 顶点已编号 0 通过 N和顶点 0 是树的根。 顶点的父级 i (1 \leq i \leq N) 是顶点 p_i.
除了这棵树之外,Snuke 还有一个最初是空的盒子和许多弹珠,并正在玩它们。 该游戏首先将一颗弹珠放置在某些顶点上,然后按如下方式进行:
- 如果顶点上有弹珠 0,将弹珠移入盒子中。
- 将每个弹珠从顶点移动到其父级(一次全部)。
- 对于两个或多个弹珠占据的每个顶点,从该顶点移除所有弹珠。
- 如果存在有一些弹珠的顶点,则转至步骤1。否则,结束游戏。
有 2^{N+1} 将弹珠放置在某些顶点上的方法。 对于他们每个人,找到 比赛结束时盒子里的弹珠数量,并计算所有这些数字的模数之和 1,000,000,007.
约束
- 1 \leq N < 2 \times 10^{5}
- 0 \leq p_i < i
部分分数
- 在测试集中值得 400 点, N < 2{,}000.
输入
输入由标准输入按以下格式给出:
N
p_1 p_2 ... p_{N}
输出
打印答案。
示例输入 1
2 0 0
示例输出 1
8
当我们在两个顶点上放置弹珠时 1 和 2,Vertex 上会有多个弹珠 0 通过步骤 2。在这种情况下,这些弹珠将被移除而不是移动到盒子中。
示例输入 2
5 0 1 1 0 4
示例输出 2
96
示例输入 3
31 0 1 0 2 4 0 4 1 6 4 3 9 7 3 7 2 15 6 12 10 12 16 5 3 20 1 25 20 23 24 23
示例输出 3
730395550
请务必计算总和模 1,000,000,007.