Задачи
Counting heaps
Counting heaps
We are given a rooted tree of \textbf{n} vertices. The vertices are to be labeled with numbers \textbf{1}, \textbf{2}, ..., \textbf{n} so that each label is unique and the heap condition holds, i.e. the label of any vertex is less than the label of its parent. How many such labellings exist? Since this number may be quite large, calculate only its remainder modulo \textbf{m}.
\InputFile
The input contains several tree descriptions. The first line contains the number of input trees \textbf{t} (\textbf{t} ≤ \textbf{250}). Each tree description begins with a line containing the size of the tree \textbf{n} (\textbf{1} ≤ \textbf{n} ≤ \textbf{500000}) and an integer \textbf{m} (\textbf{2} ≤ \textbf{m} ≤ \textbf{10^9}). \textbf{n-1} lines follow, \textbf{i}-th of which contains \textbf{p(i+1)}, the number of the parent of the \textbf{i+1}-th vertex (\textbf{1} ≤ \textbf{p(i+1)} ≤ \textbf{i}). Vertex number \textbf{1} will be the root in each tree, so its parent will not be given. Total size of the input will not exceed \textbf{50}MB.
\OutputFile
For each tree output the number of its valid labellings modulo given \textbf{m}.
Explanation for sample: The \textbf{8} possible labellings from the last example test case are as follows:
\includegraphics{https://static.e-olymp.com/content/d0/d00be050785f629da49bf2c185f11e4d95f7a9d4.jpg}
Входные данные #1
��4 3 1 0 0 0 0 0 0 1 1 4 1 0 0 0 0 0 0 1 1 1 5 1 0 0 0 0 0 0 1 2 3 4 5 1 0 0 0 0 0 0 1 1 3 3
Выходные данные #1
��2 6 1 8