← 返回题目列表

AtCoder · arc086_c

E. 走私弹珠

中文机器翻译题面 查看原题

分数: 1000 点

问题陈述

Snuke有一棵有根树 N+1 顶点。 顶点已编号 0 通过 N和顶点 0 是树的根。 顶点的父级 i (1 \leq i \leq N) 是顶点 p_i.

除了这棵树之外,Snuke 还有一个最初是空的盒子和许多弹珠,并正在玩它们。 该游戏首先将一颗弹珠放置在某些顶点上,然后按如下方式进行:

  1. 如果顶点上有弹珠 0,将弹珠移入盒子中。
  2. 将每个弹珠从顶点移动到其父级(一次全部)。
  3. 对于两个或多个弹珠占据的每个顶点,从该顶点移除所有弹珠。
  4. 如果存在有一些弹珠的顶点,则转至步骤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.