There is a tree with $n$ vertices, labeled from $1$ to $n$.

For each vertex in the tree, there may be a white piece, a black piece, or no piece. There are exactly $w$ white pieces and $b$ black pieces on the tree. Additionally, for every pair of vertices with pieces of the same color, there exists a path such that every vertex on the path contains a piece of the same color (i.e., pieces of each color form a connected component).

You can perform the following operation any number of times:

• Choose a vertex $u$ that contains a piece.
• 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 pieces of the same color, and $p_k$ has no piece.
• Move the piece from $p_1$ to $p_k$. After this, $p_1$ has no piece, and $p_k$ has a piece.

After each operation, the pieces of each color must still form a connected component.

For two initial states $S$ and $T$, we consider $S$ and $T$ to be equivalent if you can transform $S$ into $T$ using the above operations any number of times (possibly zero).

Define $f(w, b)$ as the number of equivalence classes when there are $w$ white pieces and $b$ black pieces on the tree. You need to calculate:

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

Input

The first line contains an integer $T$, representing the number of test cases.

For each test case:

The first line contains an integer $n$, representing the size of the tree.

The second line contains $n-1$ integers $fa_i$ for $i=2 \dots n$ ($1 \le fa_i < i$), representing an edge between $(fa_i, i)$ in the tree.

Output

For each test case, output a single integer representing the answer.

Examples

Input 1

2
5
1 2 3 3
10
1 2 3 4 3 6 3 8 2

Output 1

71
989

Note

For the first example:

• $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,$
• $f(4, 1) = 3.$

Constraints

For all test cases: $n \ge 2, 1 \le \sum n \le 2 \times 10^5, 1 \le fa_i < i$.