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

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

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

For each set of test data, output a line containing an integer, representing the number of possible prosperous trees, taken 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$.

samples.zip