아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

Группировки

시간 제한1초메모리 제한1024 MB

요약
한 노드와 그의 직접 부하 둘 이상으로 이루어진 크기 3 이상 k 이하의 서로 겹치지 않는 그룹을 고르는 경우의 수를 1e9+7로 나눈 나머지로 구한다.
난이도

보통10점 중 7점

유형
트리, 동적 계획법, 조합론
정답자
아직 제출이 없습니다

문제

За голову Джона Уика опять назначена награда, и лидеры одного очень влиятельного клана решили во что бы то ни стало ее получить. В клане есть nn оперативников, которые могут принять участие в охоте за целью. Поскольку всем известно, что Джон --- опасная цель, из множества оперативников было решено выбрать несколько групп размерами от 33 до kk включительно.

Все nn человек имеют в клане строгую иерархию в виде подвешенного дерева: самый опытный оперативник имеет номер 11, у каждого из остальных есть один непосредственный начальник p_i<ip\_i < i. У оперативников есть четкие правила, по которым они формируют группы. А именно, каждый оперативник готов быть в команде либо со своим непосредственным начальником, либо с несколькими своими непосредственными подчиненными, и больше ни с кем. Таким образом, любая команда будет состоять из какого-то оперативника с хотя бы двумя его непосредственными подчиненными.

Лидеры клана подозревают, что Джон заранее будет готов к большому количеству сценариев развития событий, поэтому им необходимо посчитать, сколько есть способов выбрать несколько непересекающихся групп оперативников, чтобы оценить, какие у них шансы.

Поскольку ответ на задачу может быть слишком большим, выведите его по модулю 109+710^9 + 7.

입력

В первой строке ввода через пробел даны два целых числа nn и kk --- количество оперативников и максимальное количество человек в группе (1⩽n⩽2⋅1051 \leqslant n \leqslant 2 \cdot 10^5; 3⩽k⩽53 \leqslant k \leqslant 5).

В следующей строке через пробел перечислены целые числа p_2p\_2, \ldots, p_np\_n --- номера непосредственных начальников оперативников со второго по nn-го (1⩽p_i<i1 \leqslant p\_i < i).

출력

Выведите одно целое число --- количество способов разбить оперативников на группы размерами от 33 до kk указанным образом по модулю 109+710^9 + 7.

예제3

  1. 예제 1

    입력
    3 3
    1 1
    
    예상 출력
    2
    
  2. 예제 2

    입력
    5 3
    1 1 2 2
    
    예상 출력
    3
    
  3. 예제 3

    입력
    11 4
    1 1 1 1 3 4 3 4 6 6
    
    예상 출력
    39