DZY Loves Connecting

Time Limit: 2000ms
Memory Limit: 262144KB
This problem will be judged on HDU. Original ID: 5647
64-bit integer IO format: %I64d      Java class name: Main

Description

DZY has an unrooted tree consisting of $n$ nodes labeled from $1$ to $n$.

DZY likes connected sets on the tree. A connected set $S$ is a set of nodes, such that every two nodes $u,v$ in $S$ can be connected by a path on the tree, and the path should only contain nodes from $S$. Obviously, a set consisting of a single node is also considered a connected set.

The size of a connected set is defined by the number of nodes which it contains. DZY wants to know the sum of the sizes of all the connected sets. Can you help him count it?

The answer may be large. Please output modulo $10^9 + 7$.

Input

First line contains $t$ denoting the number of testcases.
$t$ testcases follow. In each testcase, first line contains $n$. In lines $2 \sim n$, $i$th line contains $p_i$, meaning there is an edge between node $i$ and node $p_i$. ($1\le p_i \le i-1,2\le i\le n$)

($n\ge 1$, sum of $n$ in all testcases does not exceed $200000$)

Output

Output one line for each testcase, modulo $10^9 + 7$.

Sample Input

2
1
5
1
2
2
3

Sample Output

1
42

Source

Language: 
Theme: 
Share Code? 

Powered by NB231 | Current Style: .