Группировки
시간 제한1초메모리 제한1024 MB
한 노드와 그의 직접 부하 둘 이상으로 이루어진 크기 3 이상 k 이하의 서로 겹치지 않는 그룹을 고르는 경우의 수를 1e9+7로 나눈 나머지로 구한다.
문제
За голову Джона Уика опять назначена награда, и лидеры одного очень влиятельного клана решили во что бы то ни стало ее получить. В клане есть оперативников, которые могут принять участие в охоте за целью. Поскольку всем известно, что Джон --- опасная цель, из множества оперативников было решено выбрать несколько групп размерами от до включительно.
Все человек имеют в клане строгую иерархию в виде подвешенного дерева: самый опытный оперативник имеет номер , у каждого из остальных есть один непосредственный начальник . У оперативников есть четкие правила, по которым они формируют группы. А именно, каждый оперативник готов быть в команде либо со своим непосредственным начальником, либо с несколькими своими непосредственными подчиненными, и больше ни с кем. Таким образом, любая команда будет состоять из какого-то оперативника с хотя бы двумя его непосредственными подчиненными.
Лидеры клана подозревают, что Джон заранее будет готов к большому количеству сценариев развития событий, поэтому им необходимо посчитать, сколько есть способов выбрать несколько непересекающихся групп оперативников, чтобы оценить, какие у них шансы.
Поскольку ответ на задачу может быть слишком большим, выведите его по модулю .
입력
В первой строке ввода через пробел даны два целых числа и --- количество оперативников и максимальное количество человек в группе (; ).
В следующей строке через пробел перечислены целые числа , \ldots, --- номера непосредственных начальников оперативников со второго по -го ().
출력
Выведите одно целое число --- количество способов разбить оперативников на группы размерами от до указанным образом по модулю .