목서 나무

8년 전 Little B는 목서 나무를 보았다. 목서 나무는 정점이 $n$개인 트리 $T$이며, 루트가 아닌 모든 정점의 부모는 자기 번호보다 작은 번호를 가진다. 정수 $k$가 주어졌을 때, 정점이 $(n + m)$개인 루트 트리 $T'$가 다음 조건을 모두 만족하면 $T'$를 번영하는 트리라고 한다.

• $1 \leq i, j \leq n$인 모든 $(i, j)$에 대해, $T$와 $T'$에서 정점 $i$와 $j$의 최소 공통 조상의 번호가 같다.
• $1 \leq i, j \leq n + m$인 모든 $(i, j)$에 대해, $T'$에서 정점 $i$와 $j$의 최소 공통 조상의 번호는 $\max(i, j) + k$를 넘지 않는다.

모든 정점은 1번부터 번호가 매겨지며 루트의 번호는 1이다. $T'$는 루트가 아닌 모든 정점의 부모 번호가 자기 번호보다 작아야 한다는 조건을 만족할 필요가 없다.

Little B는 정점이 $(n + m)$개인 번영하는 트리의 개수를 구하려 한다. 두 트리는 어떤 정점의 부모가 서로 다르면 다른 트리로 본다. 답을 $10^9+7$로 나눈 나머지를 출력한다.

입력에는 여러 개의 테스트 데이터가 포함된다.

첫 줄에는 테스트 케이스 번호 $c$와 테스트 데이터의 개수 $t$가 주어진다. $c = 0$이면 샘플 테스트이다.

각 테스트 데이터의 첫 줄에는 정수 $n$, $m$, $k$가 주어진다. 둘째 줄에는 $n - 1$개의 정수 $f_2, f_3, \ldots, f_n$이 주어지며, $f_i$는 $T$에서 정점 $i$의 부모 번호이다.

각 테스트 데이터에 대해, 번영하는 트리의 개수를 $10^9+7$로 나눈 나머지를 한 줄에 출력한다.

모든 테스트 데이터에 대해 다음이 보장된다.

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