%LuaLaTeX
\documentclass[12pt]{article}
\input{structure.tex}
\renewcommand{\bottomtitlespace}{3cm}

\renewcommand{\header}{
	ЗИМНИ ОНЛАЙН СЪСТЕЗАНИЯ ПО ИНФОРМАТИКА\\ ``Д-р Младен Манев''\\
	31 януари 2026 г.\\
	Група C -- 7, 8 клас
}

\begin{document}

\renewcommand{\tl}{$2$ сек}
\renewcommand{\ml}{$256$ MB}
\problem{Задача C2. ЕКИПИ}

Ивка работи в строго йерархична организация, в която са назначени точно $N$ служители. Всеки служител има уникален номер -- цяло число между $1$ и $N$. Най-опитният служител е този с номер $1$, а всеки друг служител с номер $i$ между $2$ и $N$ има пряк началник, чийто номер е означен с $p_i$. 

Организацията планира да състави екипи от поне $3$ и не повече от $K$ служители. Всеки екип трябва да се състои от един служител и няколко от неговите \textbf{преки} подчинени. Освен това всеки служител трябва да бъде в най-много един екип.  

Напишете програма \textbf{\texttt{teams}}, която изчислява колко различни възможности има за съставянето на екипите. Понеже този брой може да е твърде голям, се търси остатъкът му при деление на $10^9+7$. Две възможности се считат за различни, ако броят на сформираните екипи е различен, или някой от тях има различен състав. Забележете, че без значение от структурата на йерархията, винаги има поне една възможност и тя е да не се състави нито един екип.

\subsection{Вход}
На първия ред в стандартния вход са записани стойносттите на $N$ и $K$. 
На следващия ред от входа са записани $N-1$ числа -- преките началници на служителите $p_2, p_3, \dots, p_N$.

\subsection{Изход}
На първия и единствен ред от стандартния изход, изведете едно цяло число число, равно на търсения брой различни възможности по модул $10^9+7$.

\subsection{Ограничения}
\begin{itemize}
\item $1 \le N \le 200~000$
\item $3 \le K \le 5$
\item $1 \le p_i < i$ за всяко $2 \le i \le N$
\end{itemize}

\subsection{Подзадачи}
\begin{table}[H]
	\begin{tblr}{|Q[c,m]|Q[c,m]|Q[c,m]|Q[c,m]|Q[c,m]|}
		\hline
		\textbf{Подзадача} & \textbf{Точки} & \textbf{Необходими подзадачи} & $N$ & \textbf{Допълнителни ограничения} \\
        \hline
        $0$ & $0$ & -- & -- & Примерните тестове \\ 
        \hline
		$1$ & $7$ & -- & $\leq 15$ & $K = 3$ \\ 
		\hline
		$2$ & $8$ & $1$ & $\leq 15$ & -- \\ 
		\hline
		$3$ & $9$ & -- & $\leq 200~000$ & {Броят на преките подчинени на\\ всеки служител е най-много $2$.} \\
		\hline
		$4$ & $12$ & $1$ & $\leq 100$ & $K = 3$ \\
		\hline
		$5$ & $15$ & $4$ & $\leq 1~000$ & $K = 3$ \\
		\hline
        $6$ & $18$ & $2, 5$ & $\leq 1~000$ & -- \\
		\hline
        $7$ & $31$ & $1-6$ & $\leq 200~000$ & -- \\
		\hline
	\end{tblr}
	\caption*{Точките за дадена подзадача се получават само ако се преминат успешно всички тестове, предвидени за нея и за необходимите подзадачи.}
\end{table}

\newpage

\subsection{Примери}
\begin{table}[H]
	\begin{tblr}{|l|l|X[j]|}
		\hline
		\textbf{Вход} & \textbf{Изход} & \textbf{Обяснение} \\
		\hline
		\texttt{\makecell[lt]
		{3 3\\
              1 2}
		}
		& 
		\texttt{\makecell[lt]{1}
		}
		& 
        {Тъй като няма възможност да се сформира екип от един служител и поне двама негови преки подчинени, единствената възможност е да не се сформират екипи.}
        \\
		\hline
        \texttt{\makecell[lt]
		{4 3\\
              1 1 1}
		}
		& 
		\texttt{\makecell[lt]{4}
		}
		& 
        {Трите възможни екипа са служители с номера $\{1, 2, 3\}$, $\{1, 2, 4\}$ и $\{1, 3, 4\}$.}
        \\
        \hline
        \texttt{\makecell[lt]
		{10 4\\
              1 1 1 1 2 4 2 4 2}
		}
		& 
		\texttt{\makecell[lt]{44}
		}
		& 
        {}
        \\
		\hline
	\end{tblr}
\end{table}
\FloatBarrier
	
\end{document}