F. Tokens on the Tree
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Chiaki has a tree with $$$n$$$ vertices. There might be a token colored white or black on each vertex of the tree, and there are exactly $$$w$$$ white tokens and exactly $$$b$$$ black tokens. Also, for each pair of vertices with the same color of tokens, there must have been a path between them such that every vertex on the path contains a token of the same color.

Chiaki would like to perform the following operations:

  1. Choose a vertex $$$u$$$ with a token.
  2. Choose a path $$$p_1,p_2,\dots,p_k$$$ such that $$$p_1=u$$$, all vertices $$$p_1,p_2,\dots,p_{k-1}$$$ contain a token of the same color, and there's no token in $$$p_k$$$.
  3. Move the token in $$$p_1$$$ to $$$p_k$$$. Now there's no token in $$$p_1$$$ and $$$p_k$$$ contains a token.

For two initial configurations of tokens $$$S$$$ and $$$T$$$, if Chiaki could perform the above operations several times to make $$$S$$$ become $$$T$$$, $$$S$$$ and $$$T$$$ are considered equivalent.

Let $$$f(w, b)$$$ be the number of equivalence classes (an equivalence class is a maximal set of configurations where each two of them are equivalent; all equivalence classes partition the set of all configurations), Chiaki would like to know the value of

$$$$$$\left(\sum_{w=1}^{n-1}\sum_{b=1}^{n-w} w \cdot b \cdot f(w, b) \right)\bmod (10^9+7).$$$$$$

Input

There are multiple test cases. The first line of input contains an integer $$$T$$$, indicating the number of test cases.

For each test case, the first line contains an integer $$$n$$$ ($$$2 \le n \le 2 \times 10^5$$$) – the number of vertices in the tree. The second line contains $$$n-1$$$ integers $$$p_2,p_3,\dots,p_n$$$ ($$$1 \le p_i \lt i$$$), where $$$p_i$$$ means there is an edge between vertex $$$i$$$ and vertex $$$p_i$$$.

It's guaranteed that the sum of $$$n$$$ of all test cases will not exceed $$$2 \times 10^5$$$.

Output

For each test case, output an integer denoting the value of

$$$$$$\left(\sum_{w=1}^{n-1}\sum_{b=1}^{n-w} w \cdot b \cdot f(w, b) \right)\bmod (10^9+7).$$$$$$

Example
Input
2
5
1 2 3 3
10
1 2 3 4 3 6 3 8 2
Output
71
989
Note

For the first sample, the value of $$$f(w,b)$$$ for each $$$w$$$ and $$$b$$$: $$$f(1,1)=1$$$, $$$f(1,2)=2$$$, $$$f(1,3)=3$$$, $$$f(1,4)=3$$$, $$$f(2,1)=2$$$, $$$f(2,2)=2$$$, $$$f(2,3)=1$$$, $$$f(3,1)=3$$$, $$$f(3,2)=1$$$, and $$$f(4,1)=3$$$.