Problem Description

Eight years ago, Little B saw a Sweet Osmanthus tree which was a tree \( T \) with \( n \) nodes, ensuring that the parent of any non-root node has a smaller number than itself. Given an integer \( k \), a rooted tree \( T' \) with \( n + m \) nodes is considered prosperous if and only if all the following conditions are met:

1. For any \( (i, j) \) where \( 1 \le i, j \le n \), the nearest common ancestor of nodes \( i \) and \( j \) in tree \( T \) and tree \( T' \) have the same number.
2. For any \( (i, j) \) where \( 1 \le i, j \le n + m \), in tree \( T' \), the nearest common ancestor of nodes \( i \) and \( j \) has a number not exceeding \( \max(i, j) + k \).

Note that all nodes in the trees in the problem are numbered starting from 1, with the root node numbered as 1. \( T' \) does not need to satisfy the condition that the parent of a non-root node has a smaller number than itself.

Little B wants to know how many trees with \( n + m \) nodes are prosperous, considering two trees different if and only if there exists a node with a different parent in the two trees. You only need to output the number of such trees modulo \( 10^9 + 7 \).

Input Format

This problem contains multiple test cases.

The first line of input contains two integers \( c \) and \( t \), representing the test point number and the number of test cases, respectively. \( c = 0 \) indicates that this test point is a sample.

The following lines describe each test case:

The first line of each test case contains three integers \( n \), \( m \), and \( k \).

The second line contains \( n - 1 \) integers \( f_2, f_3, \ldots, f_n \), where \( f_i \) represents the parent node number of node \( i \) in \( T \).

Output Format

For each test case, output a single integer on a line, representing the number of prosperous trees modulo \( 10^9 + 7 \).

Sample Input and Output

Input Sample #1

0 3
1 2 1

2 2 1
1
2 2 0
1

Output Sample #1

3
16
15

Input Sample #2

See the attached file tree/tree2.in.

Output Sample #2

See the attached file tree/tree2.ans.

Input Sample #3

See the attached file tree/tree3.in.

Output Sample #3

See the attached file tree/tree3.ans.

Input Sample #4

See the attached file tree/tree4.in.

Output Sample #4

See the attached file tree/tree4.ans.

Notes/Hints

[Sample Explanation #1]

For the first test case in the sample, there are three valid trees, with the sequences of parent nodes \(\{f_2, f_3\}\) being \(\{1, 1\}\), \(\{3, 1\}\), and \(\{1, 2\}\). Note that the second line of this test case is empty.

For the second and third test cases in the sample, there are 16 trees that satisfy the first condition, of which only the tree with the parent sequence \(\{4, 4, 1\}\) does not satisfy the second condition in the third test case.

[Sample Explanation #2]

This set of samples satisfies \( n \le 100 \), and in the five test cases, \( m \) does not exceed \( 0, 1, 1, 2, 2 \) respectively.

[Sample Explanation #3]

This set of samples satisfies \( k = 0 \), and in the five test cases, the first two satisfy \( n = 1 \), and the first, third, and fourth test cases satisfy \( n, m \le 100 \).

[Sample Explanation #4]

This set of samples has the first two test cases satisfying \( n = 1 \), and the first, third, and fourth test cases satisfying \( n, m \le 100 \).

[Data Range]

For all test data, it is guaranteed that: \( 1 \le t \le 15 \), \( 1 \le n \le 3 \times 10^4 \), \( 0 \le m \le 3000 \), \( 0 \le k \le 10 \), \( 1 \le f_i \le i - 1 \).

见题面 Input 部分

见题面 Output 部分