C. Virtual Tree Subsets
time limit per test
10 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You have a tree $$$T$$$ of $$$N$$$ nodes numbered $$$1$$$ to $$$N$$$, and rooted at $$$1$$$. Let $$$\texttt{lca}(x, y)$$$ denote the least common ancestor of $$$x$$$ and $$$y$$$.

A non-empty subset $$$K \in T$$$ is said to be a valid virtual tree subset if for all $$$x, y$$$ in $$$K$$$, $$$\texttt{lca}(x, y)$$$ also belongs to $$$K$$$.

We are interested in knowing the number of valid virtual tree subsets $$$K$$$ of $$$T$$$.

There are $$$2$$$ parts to this problem, denoted by subtask type $$$S$$$. You are given the tree $$$T$$$ in the form of it's parent array, i.e. you are given the values $$$P_2, P_3, ...., P_N$$$ ($$$P_i \lt i$$$) where there is an edge between $$$P_i$$$ and $$$i$$$ in the tree.

  • If $$$S = 0$$$, you only need to find the number of valid virtual tree subsets of a given tree $$$T$$$.
  • if $$$S = 1$$$, you need to find the number of valid virtual tree subsets of every "prefix" of $$$T$$$. Formally, do the following process:
    • Start with tree $$$U$$$ as the singleton node $$$1$$$.
    • For each $$$i$$$ in $$$2$$$ to $$$N$$$, add the node $$$i$$$ to $$$U$$$ connected to $$$P_i$$$. Now find the number of virtual tree subsets of $$$U$$$.

In both cases, since the answer may be large, output it modulo $$$10^9 + 7$$$.

There are multiple test cases in each file, and thus you will be given an input parameter $$$T$$$, denoting that you have to solve $$$T$$$ test cases.

Input

The first line of input contains $$$T$$$ and $$$S$$$ - the number of test cases and the subtask type respectively.

The first line of each test case contains $$$N$$$ - the number of nodes in the tree.

The second line of each test case contains $$$N - 1$$$ integers - $$$P_2, P_2, ..., P_N$$$, the parents of each node (except $$$1$$$ which is the root).

Output

If $$$S = 0$$$, output a single integer - the number of virtual tree subsets of $$$T$$$ modulo $$$10^9 + 7$$$.

If $$$S = 1$$$, output $$$N - 1$$$ integers - the number of virtual tree subsets of every "prefix" of $$$T$$$ modulo $$$10^9 + 7$$$.

Scoring

Constraints

It is guaranteed that

  • $$$1 \le T \le 10^4$$$
  • $$$S = 0$$$ or $$$S = 1$$$
  • $$$2 \le N \le 2 \cdot 10^5$$$
  • $$$1 \le P_i \lt i$$$
  • The sum of $$$N$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$
  • If in your solution you need to divide by a non-zero number, you may assume that the tests have been created such that for most solutions this number is not divisible by $$$10^9 + 7$$$.

Subtasks

  • Subtask 1 (3 points) : $$$S = 0, P_i = (i - 1)$$$.
  • Subtask 2 (8 points) : $$$S = 0, N \le 8, T \le 100$$$.
  • Subtask 3 (24 points) : $$$S = 0$$$.
  • Subtask 4 (13 points) : $$$S = 1$$$, each node has a distance of at most $$$10$$$ from root node $$$1$$$.
  • Subtask 5 (16 points) : $$$S = 1$$$, for all $$$i \gt 5000, P_i = (i - 1), T = 1$$$
  • Subtask 6 (36 points) : $$$S = 1$$$.
Examples
Input
7 0
2
1
3
1 1
4
1 2 2
5
1 1 2 3
6
1 1 1 4 3
10
1 2 1 3 1 1 6 2 6
40
1 2 1 3 4 2 4 6 6 4 9 3 13 3 8 11 4 1 1 11 21 16 9 8 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39
Output
3
6
13
22
39
384
508083434
Input
7 1
2
1
3
1 1
4
1 2 2
5
1 1 2 3
6
1 1 1 4 3
10
1 2 1 3 1 1 6 2 6
40
1 2 1 3 4 2 4 6 6 4 9 3 13 3 8 11 4 1 1 11 21 16 9 8 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39
Output
3
3 6
3 7 13
3 6 12 22
3 6 11 21 39
3 7 12 24 41 74 140 225 384
3 7 12 24 42 67 109 193 319 529 949 1561 2785 4621 8293 15501 29713 58926 117351 202086 371556 736320 1242309 2012994 3554364 6637104 12802584 25133544 49795464 99119304 197766984 395062344 789653064 578834497 157197363 313923102 627374580 254277529 508083434
Note

Sample 1

In the first test case, the tree consists of only $$$2$$$ nodes, $$$1$$$ and $$$2$$$. There are a total of $$$3$$$ non-empty subsets, i.e. $$$\{1\}, \{2\}$$$ and $$$\{1, 2\}$$$, and all of them are valid.

In the second test case, there are $$$3$$$ nodes and there are $$$7$$$ non-empty subsets. However, the subset $$$\{2, 3\}$$$ is not valid as $$$\texttt{lca(2, 3)} = 1$$$ is not in the subset.

Sample 2

In the first test case, we only need to print $$$1$$$ integer, which is the answer for the tree formed by attaching node $$$2$$$ to $$$P_2 = 1$$$. This is $$$3$$$ as we had seen above.

In the second test case, we need to print $$$2$$$ integers:

  • The answer after attaching node $$$2$$$ to $$$1$$$, which is $$$3$$$
  • The answer after attaching node $$$3$$$ to $$$1$$$ and node $$$2$$$ to $$$1$$$, which is $$$6$$$.