/ 
Time Limit: 3 sec / Memory Limit: 512 MB
配点 : 1000 点
問題文
すぬけ君は N+1 頂点の根付き木を持っています。 この木の頂点には 0 から N までの番号がついており、頂点 0 はこの木の根です。 頂点 i(1 \leq i \leq N) の親は頂点 p_i です。
すぬけ君はこの木の他に、空の箱とビー玉を使って遊んでいます。 この遊びはいくつかの頂点にビー玉をそれぞれ 1 つ置いたのち、以下の手順で進行します。
- 頂点 0 にビー玉が置かれているならば、そのビー玉を箱に移す。
- 全てのビー玉を現在の頂点から親の頂点に(同時に)移す。
- 2 つ以上のビー玉が置かれている頂点それぞれについて、その頂点に置かれているビー玉を全て取り除く。
- ビー玉が置かれている頂点が存在するならば手順 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}
出力
答えを出力せよ。
入力例 1
2 0 0
出力例 1
8
頂点 1 と頂点 2 のどちらにもビー玉を置いたとき、手順 2 により頂点 0 に複数のビー玉が置かれてしまいます。このとき、これらのビー玉は取り除かれるため箱に移動されることはありません。
入力例 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
答えを { \rm mod} 1,000,000,007 で求めてください。
Score : 1000 points
Problem Statement
Snuke has a rooted tree with N+1 vertices. The vertices are numbered 0 through N, and Vertex 0 is the root of the tree. The parent of Vertex i (1 \leq i \leq N) is Vertex p_i.
Besides this tree, Snuke also has an box which is initially empty and many marbles, and playing with them. The play begins with placing one marble on some of the vertices, then proceeds as follows:
- If there is a marble on Vertex 0, move the marble into the box.
- Move each marble from the vertex to its parent (all at once).
- For each vertex occupied by two or more marbles, remove all the marbles from the vertex.
- If there exists a vertex with some marbles, go to Step 1. Otherwise, end the play.
There are 2^{N+1} ways to place marbles on some of the vertices. For each of them, find the number of marbles that will be in the box at the end of the play, and compute the sum of all those numbers modulo 1,000,000,007.
Constraints
- 1 \leq N < 2 \times 10^{5}
- 0 \leq p_i < i
Partial Scores
- In the test set worth 400 points, N < 2{,}000.
Input
Input is given from Standard Input in the following format:
N
p_1 p_2 ... p_{N}
Output
Print the answer.
Sample Input 1
2 0 0
Sample Output 1
8
When we place a marble on both Vertex 1 and 2, there will be multiple marbles on Vertex 0 by step 2. In such a case, these marbles will be removed instead of being moved to the box.
Sample Input 2
5 0 1 1 0 4
Sample Output 2
96
Sample Input 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
Sample Output 3
730395550
Be sure to compute the sum modulo 1,000,000,007.