Problem M
King's Colors
The flag will of course consist of the King’s favorite tree, which contains $n$ nodes. The King would be happy to just have the tree colored in black and white, but for the sake of his wife the Queen, he decided that the tree will contain all the favorite colors of their $k$ children (they all have distinct favorite colors). Clearly, no two neighboring nodes can have the same color, but otherwise any coloring of the tree using exactly the $k$ colors would make a feasible flag candidate.
How many different flags are possible?
Input
The first line contains two integers $n$ and $k$ ($2 \le k \le n \le 2\, 500$), where $n$ is the number of nodes in the King’s favorite tree and $k$ is the number of children. Then follow $n-1$ lines describing the edges in the tree; the $i$’th of these lines contains a non-negative integer $p_ i < i$, meaning that node $p_ i$ is the parent of $i$.
The nodes are numbered from $0$ to $n-1$ and the tree is rooted at node $0$. Note that the embedding of the tree on the flag is already fixed, the only thing that remains is to assign colors.
Output
Output the number of different possible color assignments. The number can be quite big, so the King has requested to know the answer modulo $1\, 000\, 000\, 007$.
| Sample Input 1 | Sample Output 1 |
|---|---|
4 3 0 1 1 |
18 |
| Sample Input 2 | Sample Output 2 |
|---|---|
6 4 0 1 1 3 4 |
600 |
