За голову Джона Уика опять назначена награда, и лидеры одного очень влиятельного клана решили во что бы то ни стало ее получить. В клане есть $$$n$$$ оперативников, которые могут принять участие в охоте за целью. Поскольку всем известно, что Джон — опасная цель, из множества оперативников было решено выбрать несколько групп размерами от $$$3$$$ до $$$k$$$ включительно.
Все $$$n$$$ человек имеют в клане строгую иерархию в виде подвешенного дерева: самый опытный оперативник имеет номер $$$1$$$, у каждого из остальных есть один непосредственный начальник $$$p_i < i$$$. У оперативников есть четкие правила, по которым они формируют группы. А именно, каждый оперативник готов быть в команде либо со своим непосредственным начальником, либо с несколькими своими непосредственными подчиненными, и больше ни с кем. Таким образом, любая команда будет состоять из какого-то оперативника с хотя бы двумя его непосредственными подчиненными.
Лидеры клана подозревают, что Джон заранее будет готов к большому количеству сценариев развития событий, поэтому им необходимо посчитать, сколько есть способов выбрать несколько непересекающихся групп оперативников, чтобы оценить, какие у них шансы.
Поскольку ответ на задачу может быть слишком большим, выведите его по модулю $$$10^9 + 7$$$.
В первой строке ввода через пробел даны два целых числа $$$n$$$ и $$$k$$$ — количество оперативников и максимальное количество человек в группе ($$$1 \leqslant n \leqslant 2 \cdot 10^5$$$; $$$3 \leqslant k \leqslant 5$$$).
В следующей строке через пробел перечислены целые числа $$$p_2$$$, ..., $$$p_n$$$ — номера непосредственных начальников оперативников со второго по $$$n$$$-го ($$$1 \leqslant p_i < i$$$).
Выведите одно целое число — количество способов разбить оперативников на группы размерами от $$$3$$$ до $$$k$$$ указанным образом по модулю $$$10^9 + 7$$$.
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач успешно пройдены.
Подзадача | Баллы | Дополнительные ограничения | Необходимые подзадачи | Информация о проверке |
1 | 7 | $$$n \leqslant 15$$$; $$$k = 3$$$ | полная | |
2 | 8 | $$$n \leqslant 15$$$ | 1 | первая ошибка |
3 | 9 | $$$\mathrm{deg}(v) \leqslant 2$$$ для всех $$$v$$$ | первая ошибка | |
4 | 12 | $$$n \leqslant 100$$$; $$$k = 3$$$ | 1 | первая ошибка |
5 | 15 | $$$n \leqslant 1000$$$; $$$k = 3$$$ | 4 | первая ошибка |
6 | 18 | $$$n \leqslant 1000$$$ | 2, 5 | первая ошибка |
7 | 31 | нет | 1 – 6 | первая ошибка |
Здесь за $$$\mathrm{deg}(v)$$$ обозначено количество непосредственных подчиненных оперативника номер $$$v$$$.
3 3 1 1
2
5 3 1 1 2 2
3
11 4 1 1 1 1 3 4 3 4 6 6
39