Arpa and choosing brother free subset

3.1

26 votes
Algorithms, Dynamic Programming, Medium
Problem

Arpas family consists of n men. We can show them with a rooted tree with n vertices. Arpa wants to choose k of them for playing football but he shouldn't choose someone and his brother too. In short, there should be no direct siblings, both selected for playing football. Print in how many ways he can choose this set modulo 109+7.

Input Format

The first line contains two integers, n, k (1n105,0k100).

The second line contains n1 integers p2,p3,,pn (pi<i) -- pi is the index of the parent of i-th person.

Output Format

Print in how many ways he can choose this set modulo 109+7.

Sample Input
6 2
1 2 3 2 3
Sample Output
13
Time Limit: 2
Memory Limit: 256
Source Limit:
Explanation

Arpa can't choose {3, 5} or {4, 6} but he can choose any other pair.

Editor Image

?