Statement

You have a tree T of N nodes numbered from 1 to N, and rooted at 1. A tree is a connected graph of N nodes and N - 1 edges. Let lca(x, y) denote the least common ancestor of x and y. lca(x, y) can be defined as the node which is furthest from the root 1 and is a common node on the paths from 1 to x, and 1 to y.

A non-empty subset K in T is said to be a valid virtual tree subset if for all x, y in K, lca(x, y) also belongs to K, i.e. the lca of any 2 nodes in the subset must also be part of the subset.

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 its parent array, i.e., you are given the values P2, P3, ...., PN (Pi < i) where there is an edge between Pᵢ 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ᵢ. Now find the number of virtual tree subsets of U.

In both cases, since the answer may be large, output it modulo 109 + 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 Format

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 - P2, P3, ..., PN, the parents of each node (except 1, which is the root).

Output Format

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

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

Constraints

It is guaranteed that:

• 1 ≤ T ≤ 104
• S = 0 or S = 1
• 2 ≤ N ≤ 2 × 105
• 1 ≤ Pi < i
• The sum of N over all test cases does not exceed 2 × 105
• 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 109 + 7.

Subtasks

• Subtask 1 (3 points) : S = 0, Pi = (i - 1).
• Subtask 2 (8 points) : S = 0, N ≤ 8, T ≤ 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 > 5000, Pi = (i - 1), T = 1.
• Subtask 6 (36 points) : S = 1.

Sample 1

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
	

Explanation

Test Case 1 : 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.

Test Case 2: there are 3 nodes and there are 7 non-empty subsets. However, the subset {2,3} is not valid as lca(2, 3) = 1 is not in the subset.

Sample 2

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
	

Explanation

Test Case 1 : we only need to print 1 integer, which is the answer for the tree formed by attaching node 2 to P2 = 1. This is 3 as we had seen above.

Test Case 2 : 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.