Tokens on the Tree

아직 제출이 없습니다시간 제한1초메모리 제한256 MB

문제

Chiaki has a tree with nn vertices, labeled by integers from 11 to nn. For each vertex in the tree, there is a white token or a black token or no token at all. There are exactly ww white tokens and exactly bb black tokens. Also, for each pair of vertices with the same color of tokens, there exists 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 uu with a token.
  2. Choose a path p_1,p_2,,p_kp\_1,p\_2,\dots,p\_k such that p_1=up\_1=u, all vertices p_1,p_2,,p_k1p\_1,p\_2,\dots,p\_{k-1} contain a token of the same color, and there's no token in p_kp\_k.
  3. Move the token in p_1p\_1 to p_kp\_k. Now there's no token in p_1p\_1 and p_kp\_k contains a token.

For two initial configurations of tokens SS and TT, if Chiaki could perform the above operations several (zero or more) times to make SS become TT, then SS and TT are considered equivalent.

Let f(w,b)f(w, b) be the number of equivalence classes (that is, the maximum number of configurations that no two are equivalent). Chiaki would like to know the value of

(_w=1n1_b=1nwwbf(w,b))mod(109+7).\left(\sum\limits\_{w=1}^{n-1}\sum\limits\_{b=1}^{n-w} w \cdot b \cdot f(w, b) \right)\bmod (10^9+7)\text{.}

입력

There are multiple test cases. The first line of input contains an integer TT, indicating the number of test cases. For each test case:

The first line contains an integer nn (2n21052 \le n \le 2 \cdot 10^5): the number of vertices in the tree.

The second line contains n1n-1 integers p_2,p_3,,p_np\_2,p\_3,\ldots,p\_n (1p_i<i1 \le p\_i < i), where p_ip\_i means there is an edge between vertex ii and vertex p_ip\_i.

It is guaranteed that the sum of nn of all test cases will not exceed 21052 \cdot 10^5.

출력

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

(_w=1n1_b=1nwwbf(w,b))mod(109+7).\left(\sum\limits\_{w=1}^{n-1}\sum\limits\_{b=1}^{n-w} w \cdot b \cdot f(w, b) \right)\bmod (10^9+7)\text{.}

힌트

For the first sample, the values of f(w,b)f(w,b) for each ww and bb are: \\ f(1,1)=1f(1,1)=1, f(1,2)=2f(1,2)=2, f(1,3)=3f(1,3)=3, f(1,4)=3f(1,4)=3, \\ f(2,1)=2f(2,1)=2, f(2,2)=2f(2,2)=2, f(2,3)=1f(2,3)=1, \\ f(3,1)=3f(3,1)=3, f(3,2)=1f(3,2)=1, \\ f(4,1)=3f(4,1)=3.