B. GCN
time limit per test
1 second
memory limit per test
128 megabytes
input
standard input
output
standard output

After Da7doo7 got fired again, he decided to count things for a living. Then, he struggled with this problem, so he called you for help.

You are given a tree consisting of $$$n$$$ nodes.

  • Let $$$\langle a, b \rangle$$$ be the set containing all nodes of the simple path between nodes $$$a$$$ and $$$b$$$, where $$$a \lt b$$$.
  • Let $$$GCN[\langle a, b \rangle, \langle c, d \rangle]$$$ be the number of nodes that are in both of the sets $$$\langle a, b \rangle$$$ and $$$\langle c, d \rangle$$$.

Your task is to find the sum of $$$GCN$$$ over all different unordered pairs of distinct sets in the given tree, modulo $$$10^9+7$$$.

Note
  • Do not count $$$GCN[\langle a, b \rangle, \langle a, b \rangle]$$$.
  • $$$GCN[\langle a, b \rangle, \langle c, d \rangle]$$$ and $$$GCN[\langle c, d \rangle, \langle a, b \rangle]$$$ are considered the same pair of sets, do not count them twice.
Input

The first line of the input contains an integer $$$T$$$ $$$(1\le T\le 10^5)$$$ denoting the number of test cases.

The first line of each test case contains an integer $$$n$$$ $$$(2\le n \le 5\cdot 10^5)$$$ — the number of nodes in the tree.

The second line of each test case contains $$$n-1$$$ integers $$$p_2, \ldots, p_n$$$ $$$(1\le p_i \le n)$$$ — indicating that there is an edge between nodes $$$i$$$ and $$$p_i$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5\cdot 10^5$$$.

Output

For each test case, print the answer in a single line.

Example
Input
2
4
1 2 3
4
1 1 1
Output
26
24