Eight years ago, Little B saw an osmanthus tree, which is a tree ~T~ with ~n~ vertices, where the parent vertex of any non-root vertex in ~T~ has a smaller label than its own. Given an integer ~k~, a rooted tree ~T'~ with ~(n + m)~ vertices is prosperous if and only if the following conditions are met:

• For any ~(i, j)~ with ~1 \leq i, j \leq n~, the lowest common ancestor of vertices ~i~ and ~j~ in ~T~ and ~T'~ has the same label.
• For any ~(i, j)~ with ~1 \leq i, j \leq n + m~, the label of the lowest common ancestor of vertices ~i~ and ~j~ in ~T'~ does not exceed ~\max(i, j) + k~.

Note that all vertices in the trees are labeled starting from ~1~, and the label of the root vertex is ~1~. ~T'~ does not need to satisfy the condition that the parent vertex of any non-root vertex has a smaller label than its own.

Little B wants to know how many trees with ~(n + m)~ vertices are prosperous. Two trees are considered different if there exists a vertex whose parent vertex is different in the two trees. Output the number of solutions modulo ~(10^9 + 7)~.

Input Specification

This problem has multiple test data sets.

The first line of the input contains two integers ~c ~ and ~t~, which represent the test case number and the number of test data sets. ~c = 0~ represents that this test case is a sample test.

Then, each set of test data is given as input in order. For each set of test data:

The first line of the input contains three integers ~n~, ~m~, and ~k~.

The second line of the input contains ~n - 1~ integers ~f_2, f_3, ..., f_n~, where ~f_i~ represents the label of the parent vertex of vertex ~i~ in ~T~.

Output Specification

For each set of test data, output a line containing an integer, representing the number of possible prosperous trees, taken modulo ~(10^9+7)~.

Sample Input 1

0 3
1 2 1
2 2 1
1
2 2 0
1

Sample Output 1

3
16
15

Explanation for Sample Output 1

For the first set of test data in the sample, there are three valid trees, with parent sequences of ~\{f_2, f_3\}~ being ~\{1, 1\}~, ~\{3, 1\}~, and ~\{1, 2\}~, respectively. Note that the second line in this set of test data is blank.

For the second and third sets of test data in the sample, there are a total of ~16~ trees that satisfy the first condition. Among them, only the tree with parent sequence ~\{4, 4, 1\}~ does not satisfy the second condition in the third set of test data.

Additional Samples

Sample inputs and outputs can be found here.

• Sample 2 (ex_tree2.in and ex_tree2.ans) satisfies ~n \leq 100~, and for the five sets of test data, ~m~ does not exceed ~0, 1, 1, 2, 2~, respectively.
• Sample 3 (ex_tree3.in and ex_tree3.ans) satisfies ~k = 0~. The first two sets of test data satisfy ~n = 1~, and the first, third, and fourth out of the five sets of test data satisfy ~n,m \leq 100~.
• Sample 4 (ex_tree4.in and ex_tree4.ans). The first two sets of test data of this sample satisfy ~n = 1~, and the first, third, and fourth sets of test data satisfy ~n,m \leq 100~.

Problem Constraints

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

Test ID	~n\le~	~m \le~	~k\le~
~1,2~	~4~	~4~	~10~
~3~	~3\times 10^4~	~0~
~4~	~10^2~	~1~
~5~	~3\times 10^4~
~6~	~10^2~	~2~
~7~	~3\times 10^4~
~8,9~	~1~	~10^2~	~0~
~10~		~3000~
~11~		~10^2~	~10~
~12~		~3000~
~13,14~	~10^2~	~10^2~	~0~
~15,16~	~3\times 10^4~	~3000~
~17,18~	~10^2~	~10^2~	~10~
~19,20~	~3\times 10^4~	~3000~