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