Osmanthus Tree

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$.

All vertices are labeled starting from $1$, and the root has label $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 different if there is a vertex whose parent differs between the two trees. Output the count modulo $10^9+7$.

The input contains multiple test data sets.

The first line contains two integers $c$ and $t$, where $c$ is the test case number and $t$ is the number of test data sets. If $c = 0$, this is a sample test.

Each test data set starts with a line containing three integers $n$, $m$, and $k$. The next line contains $n - 1$ integers $f_2, f_3, \ldots, f_n$, where $f_i$ is the label of the parent vertex of vertex $i$ in $T$.

For each test data set, output one line containing the number of prosperous trees modulo $10^9+7$.

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$