You are given a rooted tree with vertices. The root of the tree is vertex .
For each vertex , you need to choose a number c_v equal to either or . Such a choice of numbers will be called a coloring of the tree.
For each vertex , consider the unique path in the tree from vertex to vertex . Let s_v be the sum of all numbers c_u on this path, including vertices and .
A coloring is called correct if all numbers s_1, s_2, \ldots, s_n are pairwise distinct, that is, no two of them are equal.
Count the number of correct colorings of the tree.
Since the answer may be very large, output it modulo 10^9 + 7.
The first line contains one integer (1 \le t \le 10^4) — the number of test cases.
Each test case consists of two lines.
The first line of each test case contains one integer (2 \le n \le 2 \cdot 10^5) — the number of vertices in the tree.
The second line contains n-1 integers p_2, p_3, \ldots, p_n (1 \le p_i < i), where p_i is the parent of vertex .
This means that for each from to , vertices p_i and are connected by an edge, and vertex p_i is closer to the root.
It is guaranteed that the sum of over all test cases does not exceed 2 \cdot 10^5.
For each test case, output one integer — the number of correct colorings of the tree modulo 10^9 + 7.
Example 1
Example 2
Example 3
In the first example, vertices and are children of the root.
The following correct colorings are possible: \{1, 1, 2\}, \{1, 2, 1\}, \{2, 1, 2\}, \{2, 2, 1\}.
So, the answer is .
A child of vertex is a vertex such that p_u = v.
A leaf is a vertex that has no children.
The distance between two vertices of a tree is the number of edges on the unique path between them.
( points): n \le 10 and t = 1.
( points): each vertex has at most one child and t = 1.
( points): each vertex is at distance at most edges from the root and t = 1.
( points): the tree has at most one vertex with exactly two children; all other vertices have at most one child, and t = 1.
( points): only the root may have more than one child and t = 1.
( points): the number of leaves does not exceed and t = 1.
( points): the number of vertices with exactly two children does not exceed and t = 1.
( points): n \le 1000.
( points): No additional constraints.