#216506. [UOI 2026] Color the Tree

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

For each vertex , you need to choose a number 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 be the sum of all numbers on this path, including vertices and .

A coloring is called correct if all numbers 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 .

The first line contains one integer --- the number of test cases.

Each test case consists of two lines.

The first line of each test case contains one integer --- the number of vertices in the tree.

The second line contains integers , where is the parent of vertex .

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

It is guaranteed that the sum of over all test cases does not exceed .

For each test case, output one integer --- the number of correct colorings of the tree modulo .

样例输入 1

1
3
1 1

样例输出 1

4

样例输入 2

1
4
1 2 3

样例输出 2

16

样例输入 3

1
7
1 1 2 2 3 3

样例输出 3

0

In the first example, vertices and are children of the root.

The following correct colorings are possible: , , , .

So, the answer is .

Scoring

A child of vertex is a vertex such that .

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): and .
• ( points): each vertex has at most one child and .
• ( points): each vertex is at distance at most edges from the root and .
• ( points): the tree has at most one vertex with exactly two children; all other vertices have at most one child, and .
• ( points): only the root may have more than one child and .
• ( points): the number of leaves does not exceed and .
• ( points): the number of vertices with exactly two children does not exceed and .
• ( points): .
• ( points): No additional constraints.