树上游走(Tree Walk)

题目描述

所谓随机游走，是指从一个指定的起点出发，随机地（以相等的概率）从当前点的邻居中选取一个点，移动到该点，不断重复上述过程，直到走到指定的终点为止。

给定一棵 $n$ 个点的树，$1$ 号点为根。请计算，在起点与终点都是随机选取的情况下，完成一次随机游走，期望需要多少步？

输入格式

第一行：单个正整数 $n$。

第二行：$n-1$ 个正整数 $p_2, p_3, \cdots, p_n$，表示 $2$ 号点到 $n$ 号点的父亲编号，保证 $p_i < i$。

输出格式

设需要输出的有理数为 $P/Q$，且 $P$ 和 $Q$ 互素，则输出一个整数 $P \cdot Q' \bmod {10^9+7}$，其中 $Q' \cdot Q \equiv 1 \pmod{10^9+7}$。

样例输入 #1

3
1 1

样例输出 #1

777777785

样例说明

1→1、2→2、3→3：期望 0 步；2→1、3→1：期望 1 步；1→2、1→3：期望 3 步；2→3、3→2：期望 4 步；平均期望：16/9。

数据范围

• 对于 30% 的数据，$1 \le n \le 200$；
• 对于 60% 的数据，$1 \le n \le 5000$；
• 对于 100% 的数据，$1 \le n \le 100000$。

知识点与难度

本题涉及的知识点从属于 GESP 6级（树、概率期望、模逆元），难度等级：⭐⭐⭐⭐⭐。