All Tracks Algorithms Dynamic Programming Dynamic Programming and Bit Masking Problem

Arpa and choosing brother free subset
/

Algorithms, Dynamic Programming, Dynamic Programming and Bit Masking

Problem
Editorial
Analytics

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 $$10^9+7$$.

Input Format

The first line contains two integers, n, k (\(1 \leq n \leq 10^5, 0 \leq k \leq 100\)).

The second line contains $$n-1$$ integers \(p_2, p_3, \ldots, p_n\) (\(p_i < i\)) -- $$p_i$$ is the index of the parent of $$i$$-th person.

Output Format

Print in how many ways he can choose this set modulo $$10^9+7$$.

SAMPLE INPUT
6 2
1 2 3 2 3
SAMPLE OUTPUT
13
Explanation

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

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

Best Submission

Similar Problems

Contributors

This Problem was Asked in

Initializing Code Editor...
Notifications
View All Notifications

?