配点 : $1000$ 点

問題文

すぬけ君は $N+1$ 頂点の根付き木を持っています。 この木の頂点には $0$ から $N$ までの番号がついており、頂点 $0$ はこの木の根です。 頂点 $i(1 \leq i \leq N)$ の親は頂点 $p_i$ です。

すぬけ君はこの木の他に、空の箱とビー玉を使って遊んでいます。 この遊びはいくつかの頂点にビー玉をそれぞれ $1$ つ置いたのち、以下の手順で進行します。

1. 頂点 $0$ にビー玉が置かれているならば、そのビー玉を箱に移す。
2. 全てのビー玉を現在の頂点から親の頂点に(同時に)移す。
3. $2$ つ以上のビー玉が置かれている頂点それぞれについて、その頂点に置かれているビー玉を全て取り除く。
4. ビー玉が置かれている頂点が存在するならば手順 1 へ、そうでなければ遊びを終了する。

ビー玉の置き方は $2^{N+1}$ 通りあります。 これらそれぞれの場合について 遊びが終了したときに箱に入っているビー玉 の数を求め、その和を ${\rm mod} 1,000,000,007$ で求めてください。

制約

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

部分点

• $400$ 点分のデータセットでは $N < 2000$ が成立する

入力

入力は以下の形式で標準入力から与えられる。

$N$

$p_1$ $p_2$ $...$ $p_{N}$

出力

答えを出力せよ。

2
0 0

8

頂点 $1$ と頂点 $2$ のどちらにもビー玉を置いたとき、手順 $2$ により頂点 $0$ に複数のビー玉が置かれてしまいます。このとき、これらのビー玉は取り除かれるため箱に移動されることはありません。

5
0 1 1 0 4

96

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

答えを ${ \rm mod} 1,000,000,007$ で求めてください。