P16175 [ICPC 2014 NAIPC] Cheats

Cosmo 正在玩一款鲜为人知的《塞尔达传说》系列最新作《天剑·黄昏时空之影》。在这款游戏中，玩家需要作为年轻的冒险者林克完成全部 $n$ 个目标。然而，某些目标必须在其他目标之前完成！每个目标 $i$（$i = 2..n$）都有一个前置目标 $P_i$，必须在 $i$ 之前完成。当然，第一个目标（总是编号 1）没有前置目标。依赖关系不会形成循环，即不存在间接依赖于自身的目标。 然而，与所有游戏一样，这款游戏中也有隐藏的作弊码。对于每个目标 $i = 2..n$，都有一个作弊码，允许它在其前置目标之前完成！但是，事情不能太出格。如果目标 $i$ 的作弊码被使用，那么目标 $i$ 不需要在其前置目标 $P_i$ 之后完成，而只需在其前置目标的前置目标 $P_{P_i}$ 之后完成即可（如果 $P_i = 1$，则它可以在任何时刻完成，因为目标 1 没有前置目标）。此外，多个作弊码靠得太近可能会导致不可预测的效果，因此每个目标最多只能涉及一次作弊码的使用。换句话说，如果你对目标 $i$ 使用作弊码，使其可以在其前置目标 $P_i$ 之前完成，那么你就不能对 $P_i$ 使用作弊码，也不能对任何以 $i$ 为前置目标的其他目标使用作弊码。 Cosmo 希望在至多使用 $k$ 次作弊码的情况下完成游戏。在满足这些约束的条件下，他有多少种不同的完成所有 $n$ 个目标的顺序？由于这个值可能非常大，请输出它对 $10^9+7$ 取模的结果。

输入中有多个测试用例。每个测试用例的第一行包含两个整数 $n$（$1 \leq n \leq 200$）和 $k$（$0 \leq k < n$），表示 Cosmo 必须完成的目标数量（$n$）和他愿意使用的最大作弊次数（$k$）。下一行包含 $n-1$ 个空格分隔的整数 $p$（$1 \leq p \leq n$），表示目标 2, 3, ..., $n$ 的前置目标（跳过目标 1，因为它没有前置目标）。输入以一行两个 0 结束。测试数据大小约 13 KB。

对于每个测试用例，输出一个整数，表示 Cosmo 在使用不超过 $k$ 次作弊码的情况下，能够完成所有 $n$ 个目标的方案数。输出该数字对 $10^9+7$ 取模的结果。不要输出任何空格，也不要在答案之间打印空行。

下表列出了在样例输入/输出中，Cosmo 使用至多一次作弊码完成所有目标的所有顺序。 :::align{center}  ::: 翻译由 DeepSeek V3.2 完成