题目描述

You are given a rooted tree with $n$ vertices. The root of the tree is vertex $1$.

For each vertex $v$, you need to choose a number $c_v$ equal to either $1$ or $2$. Such a choice of numbers will be called a coloring of the tree.

For each vertex $v$, consider the unique path in the tree from vertex $1$ to vertex $v$. Let $s_v$ be the sum of all numbers $c_u$ on this path, including vertices $1$ and $v$.

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 $t$ $(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 $n$ $(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 $i$.

This means that for each $i$ from $2$ to $n$, vertices $p_i$ and $i$ are connected by an edge, and vertex $p_i$ is closer to the root.

It is guaranteed that the sum of $n$ 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$.

1
3
1 1

4

1
4
1 2 3

16

1
7
1 1 2 2 3 3

0

提示

In the first example, vertices $2$ and $3$ 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 $4$.

Scoring

A child of vertex $v$ is a vertex $u$ 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.

• ($11$ points): $n \le 10$ and $t = 1$.
• ($6$ points): each vertex has at most one child and $t = 1$.
• ($7$ points): each vertex is at distance at most $2$ edges from the root and $t = 1$.
• ($8$ points): the tree has at most one vertex with exactly two children; all other vertices have at most one child, and $t = 1$.
• ($12$ points): only the root may have more than one child and $t = 1$.
• ($13$ points): the number of leaves does not exceed $3$ and $t = 1$.
• ($11$ points): the number of vertices with exactly two children does not exceed $20$ and $t = 1$.
• ($15$ points): $n \le 1000$.
• ($17$ points): No additional constraints.