The Osmanthus Tree (tree) that Little B saw eight years ago was a tree $T$ with $n$ nodes, where the parent of every non-root node has a smaller index than itself. Given an integer $k$, a rooted tree $T'$ with $(n + m)$ nodes is called "prosperous" if and only if the following conditions are satisfied:

1. For any pair $(i, j)$ such that $1 \le i, j \le n$, the lowest common ancestor of nodes $i$ and $j$ in tree $T$ and tree $T'$ has the same index.
2. For any pair $(i, j)$ such that $1 \le i, j \le n + m$, the index of the lowest common ancestor of nodes $i$ and $j$ in tree $T'$ does not exceed $\max(i, j) + k$.

Note that in this problem, all nodes in all trees are indexed starting from 1, and the root node is always 1. $T'$ does not need to satisfy the condition that the parent of a non-root node has a smaller index than itself.

Little B wants to know how many prosperous trees with $(n + m)$ nodes exist. Two trees are considered different if and only if there exists at least one node that has a different parent in the two trees. Output the number of such trees modulo $(10^9 + 7)$.

Input

The input is read from the file tree.in.

There are multiple test cases. The first line contains two integers $c$ and $t$, representing the test case ID and the number of test cases, respectively. $c = 0$ indicates that the test case is a sample.

For each test case: The first line contains three integers $n, m, k$. The second line contains $n - 1$ integers $f_2, f_3, \dots, f_n$, where $f_i$ represents the parent of node $i$ in $T$.

Output

The output is written to the file tree.out.

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

Examples

Input 1

1 0 3
2 1 2 1
3
4 2 2 1
5 1
6 2 2 0
7 1

Output 1

3
16
15

Note 1

For the first test case in the sample, there are three valid trees. The sequences of parents $\{f_2, f_3\}$ for each node are $\{1, 1\}$, $\{3, 1\}$, and $\{1, 2\}$ respectively. Note that the second line of this test case is empty.

For the second and third test cases, there are 16 trees that satisfy the first condition. Among them, only the tree with the parent sequence $\{4, 4, 1\}$ does not satisfy the second condition in the third test case.

Input 2

2 5 0
(See tree/tree2.in)

Output 2

(See tree/tree2.ans)

Note 2

This sample satisfies $n \le 100$, and $m$ does not exceed $0, 1, 1, 2, 2$ across the five test cases.

Input 3

3 5 0
(See tree/tree3.in)

Output 3

(See tree/tree3.ans)

Note 3

This sample satisfies $k = 0$. The first two test cases satisfy $n = 1$, and the first, third, and fourth test cases satisfy $n, m \le 100$.

Input 4

4 5 0
(See tree/tree4.in)

Output 4

(See tree/tree4.ans)

Note 4

The first two test cases satisfy $n = 1$, and the first, third, and fourth test cases satisfy $n, m \le 100$.

Constraints

For all test cases, 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$, and $1 \le f_i \le i - 1$.