题目描述

给定一棵有 $n$ 个顶点的有根树，树根为顶点 $1$。

对于每个顶点 $v$，你需要选择一个数字 $c_v$，其值为 $1$ 或 $2$。这样的数字选择方案称为该树的一种涂色。

对于每个顶点 $v$，考虑树中从顶点 $1$ 到顶点 $v$ 的唯一路径。令 $s_v$ 为该路径上所有顶点对应的数字 $c_u$ 之和，包括顶点 $1$ 和 $v$ 自身。

如果所有 $s_1, s_2, \ldots, s_n$ 两两不同（即没有两个值相等），则称该涂色是正确的。

请你计算这棵树正确的涂色方案数量。

由于答案可能很大，请将其对 $10^9 + 7$ 取模后输出。

输入格式

第一行包含一个整数 $t$ $(1 \le t \le 10^4)$ —— 测试数据的组数。

每组测试数据由两行组成。

每组数据的第一行包含一个整数 $n$ $(2 \le n \le 2 \cdot 10^5)$ —— 树中顶点的个数。

第二行包含 $n-1$ 个整数 $p_2, p_3, \ldots, p_n$ $(1 \le p_i < i)$，其中 $p_i$ 是顶点 $i$ 的父顶点。

这意味着对于每个 $i$ 从 $2$ 到 $n$，顶点 $p_i$ 与顶点 $i$ 之间有一条边，且顶点 $p_i$ 离根更近。

保证所有测试数据的 $n$ 之和不超过 $2 \cdot 10^5$。

输出格式

对于每组测试数据，输出一个整数 —— 该树正确的涂色方案数量对 $10^9 + 7$ 取模的结果。

输入输出样例 #1

输入 #1

1
3
1 1

输出 #1

4

输入输出样例 #2

输入 #2

1
4
1 2 3

输出 #2

16

输入输出样例 #3

输入 #3

1
7
1 1 2 2 3 3

输出 #3

0

说明/提示

在第一个样例中，顶点 $2$ 和 $3$ 是根的子顶点。

以下涂色方案是正确的：$\{1, 1, 2\}$，$\{1, 2, 1\}$，$\{2, 1, 2\}$，$\{2, 2, 1\}$。

因此答案为 $4$。

计分

一个顶点 $v$ 的子顶点是指满足 $p_u = v$ 的顶点 $u$。

叶子是指没有子顶点的顶点。

树中两个顶点之间的距离是指它们之间唯一路径上的边数。

• （$11$ 分）：$n \le 10$ 且 $t = 1$。
• （$6$ 分）：每个顶点至多有一个子顶点，且 $t = 1$。
• （$7$ 分）：每个顶点到根的距离不超过 $2$ 条边，且 $t = 1$。
• （$8$ 分）：树中至多有一个顶点恰好拥有两个子顶点；其他所有顶点至多有一个子顶点，且 $t = 1$。
• （$12$ 分）：只有根可以拥有多于一个子顶点，且 $t = 1$。
• （$13$ 分）：叶子的数量不超过 $3$，且 $t = 1$。
• （$11$ 分）：恰好拥有两个子顶点的顶点数量不超过 $20$，且 $t = 1$。
• （$15$ 分）：$n \le 1000$。
• （$17$ 分）：无额外限制。

翻译由 DeepSeek V4 Pro 完成