Counting k-Level LCA p‐Tuples in a Rooted Tree

You are given a rooted tree with n nodes (the root is node 1). A p‐tuple of vertices (a₁, a₂, …, a_p) with 1 ≤ a₁ < a₂ < … < a_p ≤ n is called a k‐level LCA p‐tuple if there exists a vertex x such that for every ordered strictly increasing k-tuple b ⊂ a the lowest common ancestor of the k vertices (denoted by \(\operatorname{LCA}(b_1, b_2, \dots, b_k)\)) is x. In other words, if we denote \(\operatorname{LCA}_{i=1}^{k}\{b_i\}\) as the common LCA of the chosen k vertices, then the condition is:

[ \text{For every } b \subset a \text{ with } |b|=k, \quad \operatorname{LCA}_{i=1}^{k}{b_i} = x. ]

It can be shown that the condition forces the actual lowest common ancestor of the entire set \(a\) to be \(x\) and in particular, \(x\) must be one of the chosen vertices. Moreover, note that if in the set \(a\) a complete group of k vertices comes from a single subtree of x (i.e. one child of \(x\)), then the LCA of that group will lie strictly below \(x\). Hence, for a p-tuple \(a\) with \(\operatorname{LCA}(a)=x\) to have the required property, for every child \(y\) of \(x\) the number of vertices in \(a\) taken from the subtree of \(y\) must be at most \(k-1\>.

Your task is to count the number of k‐level LCA p‐tuples in the tree modulo \(10^9+7\).

Hint: For a fixed vertex \(x\), if you require \(\operatorname{LCA}(a)=x\) then \(x\) must be chosen and the remainder \(p-1\) vertices are chosen from the subtrees of \(x\) in such a way that from each child subtree at most \(k-1\) vertices are taken. If the size of the subtree rooted at a child \(y\) is \(S_y\), then there are \(\binom{S_y}{r}\) ways to choose \(r\) vertices from that subtree. Sum over all children by performing a convolution limiting each group to at most \(k-1\) vertices and with overall total \(p-1\) vertices.

inputFormat

The first line contains three integers: n, k and p (1 ≤ n ≤ N, 1 ≤ k, p ≤ n, where N is the maximum number of nodes as specified by the constraints).

The second line contains n-1 integers. For every i from 2 to n, the (i-1)th number denotes the parent of node i (it is guaranteed that the tree is rooted at node 1).

Note: For n=1, the second line is omitted.

outputFormat

Output a single integer, the number of k‐level LCA p‐tuples in the tree modulo \(10^9+7\).

sample

3 2 2
1 1

2