Hide

Problem B
Cheats

Cosmo is busy playing the little-known latest installment in the Legend of Zelda series of video games, Skyward Wind Mask of Twilight Time. In this game, the player must complete all $n$ objectives as the young adventurer Link. However, some objectives must be done before others! Each objective $i$, $i = 2 \ldots n$, has a prerequisite, $P_ i$, which must be completed before $i$. Of course, the first objective (always number $1$) has no prerequisite. There are no cycles of dependencies which would cause an objective to indirectly depend on itself.

Like all games, however, this game has hidden cheats. There is one cheat for each objective $i = 2 \ldots n$ which allows it to be completed before its prerequisite! However, things still can’t be done too much out of order. If objective $i$’s cheat is used, then instead of objective $i$ being completed after its prerequisite $P_ i$, it just has to be completed after its prerequisite’s prerequisite, $P_{P_ i}$ (unless $P_ i = 1$, in which case it can be completed at any point, since objective $1$ has no prerequisite). Furthermore, using multiple cheats too close to each other can lead to unpredictable effects, so each objective can be involved in at most one use of a cheat. In other words, if you use a cheat on objective $i$ so that you can complete it before its prerequisite $P_ i$, then you can’t use a cheat on $P_ i$, nor on any other objective that has $i$ as a prerequisite.

Cosmo would like to complete the game while exploiting at most $k$ cheats. In how many different orders can he complete all $n$ objectives, subject to these constraints? As this value can be very large, output it modulo $10^9+7$.

Input

There will be up to 150 test cases in the input. Each test case will begin with two integers $n$ ($1 \le n \le 200$) and $k$ ($0 \le k < n$), indicating the number of objectives Cosmo must complete ($n$) and the maximum number of cheats he’s willing to use ($k$). On the next line will be $n-1$ space-separated integers $p$ ($1 \le p \le n$), indicating the prerequisite objective for objectives $2, 3, \ldots , n$ (skipping $1$, since objective 1 has no prerequisite). The input will end with a line with two 0s.

Output

For each test case, output a single integer, which indicates the number of ways Cosmo can achieve all $n$ objectives while using $k$ or fewer cheats. Output this number modulo $10^9+7$.

Explanation of Sample Input/Output

This table lists all of the orders in which Cosmo can achieve all of the objectives for the Sample Input/Output using at most one cheat.

  No Cheats  | 2's Cheat  | 3's Cheat  | 4's Cheat  | 5's Cheat
-------------+------------+------------+------------+-----------
  1 2 3 5 4  | 2 1 3 5 4  | 3 1 2 5 4  | 1 2 3 4 5  | 5 1 2 3 4
  1 2 5 3 4  | 2 1 5 3 4  | 3 1 5 2 4  | 1 2 4 3 5  | 5 1 2 4 3
  1 2 5 4 3  | 2 1 3 4 5  | 3 1 5 4 2  | 1 2 4 5 3  | 5 1 3 2 4
  1 3 2 5 4  |            |            | 1 3 2 4 5  | 5 1 3 4 2
  1 3 5 2 4  |            |            | 1 3 4 2 5  | 5 1 4 2 3
  1 3 5 4 2  |            |            | 1 3 4 5 2  | 5 1 4 3 2
  1 5 2 3 4  |            |            | 1 4 2 3 5  | 5 4 1 2 3
  1 5 2 4 3  |            |            | 1 4 2 5 3  | 5 4 1 3 2
  1 5 3 2 4  |            |            | 1 4 3 2 5  |
  1 5 3 4 2  |            |            | 1 4 3 5 2  |
  1 5 4 2 3  |            |            | 1 4 5 2 3  |
  1 5 4 3 2  |            |            | 1 4 5 3 2  |
Sample Input 1 Sample Output 1
5 1
1 1 5 1
0 0
38

Please log in to submit a solution to this problem

Log in