Prosperous Tree Count

Eight years ago, Little B saw an osmanthus tree which is a tree \(T\) with \(n\) nodes. The tree \(T\) satisfies the following property: for every non‐root node, the parent’s label is smaller than its own label. Now, given an integer \(k\), we call a rooted tree \(T'\) with \(n+m\) nodes prosperous if and only if the following conditions are both satisfied:

1. For every pair \(1 \le i,j \le n\), the label of the lowest common ancestor (LCA) of nodes \(i\) and \(j\) in \(T\) is equal to that in \(T'\). (In other words, the structure among the first \(n\) nodes is preserved.)
2. For every pair \(1 \le i,j \le n+m\), if \(\ell=\mathrm{LCA}(i,j)\) in \(T'\), then it must hold that \(\ell \le \max(i,j)+k\). (Here, all nodes are labeled from 1 to \(n+m\), and the root has label 1.)

Note: In all trees, nodes are numbered starting from 1 and the root is always 1. The tree \(T'\) is not required to satisfy that a non-root node’s parent has a smaller number than itself.

Your task is to count how many different prosperous trees \(T'\) there are. Two trees are considered different if there exists a node whose parent is different in the two trees. Since the answer might be very large, output it modulo \(10^9+7\).

inputFormat

The input begins with three integers \(n\), \(m\), and \(k\) \( (1 \le n \le N,\ m \ge 1)\). Then, in the next \(n-1\) lines (or in one line containing \(n-1\) integers), the tree \(T\) is described: the \(i\)th number (for \(i=2,3,\dots,n\)) is the parent of node \(i\) in \(T\). It is guaranteed that for every non-root node in \(T\) the parent’s label is less than its own label.

(The constraints are such that a brute force/backtracking approach over the additional \(m\) nodes is feasible.)

outputFormat

Output a single integer representing the number of prosperous trees \(T'\) modulo \(10^9+7\).

sample

1 1 0

1