题目描述

すぬけ君有一棵有 $N+1$ 个节点的有根树。这棵树的节点编号为 $0$ 到 $N$，其中节点 $0$ 是根。对于每个 $i$（$1 \leq i \leq N$），节点 $i$ 的父节点是 $p_i$。

すぬけ君除了这棵树之外，还用空箱子和弹珠来玩游戏。这个游戏的玩法如下：首先在若干个节点上各放一个弹珠，然后按照以下步骤进行：

1. 如果节点 $0$ 上有弹珠，将该弹珠移到箱子里。
2. 把所有弹珠从当前节点同时移动到父节点上。
3. 对于每个有两个及以上弹珠的节点，将这些弹珠全部移除。
4. 如果仍然存在有弹珠的节点，则回到第 1 步，否则游戏结束。

由于每种弹珠的放法有 $2^{N+1}$ 种，请你计算所有情况下游戏结束时箱子中的弹珠数之和，并对 $1,000,000,007$ 取模后输出。

输入格式

输入为一行，格式如下：

$N\ p_1\ p_2\ \cdots\ p_N$

输出格式

输出答案。

样例 1

输入

2
0 0

输出

8

样例 2

输入

5
0 1 1 0 4

输出

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

输出

730395550

说明/提示

限制条件

• $1 \leq N < 2 \times 10^5$
• $0 \leq p_i < i$

部分得分

• 有 $400$ 分的数据中 $N < 2000$

样例说明 1

当节点 $1$ 和节点 $2$ 都放有弹珠时，执行第 2 步后，节点 $0$ 会有多个弹珠。此时，这些弹珠会被移除，因此不会放进箱子里。

样例说明 3

请你将答案对 $1,000,000,007$ 取模后输出。

由 ChatGPT 5 翻译