Sasha recently moved into a multi-story building. The building has a total of $n$ floors, numbered from $1$ to $n$. There is exactly one resident living on each floor. Between the floors, there are $n - 1$ staircases, and these staircases are not necessarily built between adjacent floors. It is known that for every floor except the first, there is exactly one staircase leading to a lower floor. For the $i$-th floor ($2 \le i \le n$), this staircase leads to the floor numbered $p_i$.

Sasha plans to solve $k$ tasks numbered from $1$ to $k$. For the task with number $i$, Sasha has calculated that it is most optimal to solve it on the floor numbered $x_i$. Since the tasks are different from each other, all values of $x_i$ are distinct.

It is boring to solve tasks alone, so for each task, Sasha wants to invite at least one resident to solve it together. However, the residents of the building really dislike climbing stairs and are only willing to descend to the floors where the tasks will be solved. Therefore, Sasha can invite a resident from floor $j$ to solve task $i$ only if there is a way to reach floor $x_i$ from floor $j$, using several, possibly zero, staircases that each time lead to a floor with a lower number. Thus, a resident from floor $j$ can solve task $i$ only if $j = x_i$ or $p_j = x_i$, or $p_{p_j} = x_i$, and so on.

Residents really dislike descending the stairs unnecessarily. Therefore, if Sasha invites a certain set of people to solve a task, they will only be willing to gather to solve the task on the \textbf{highest floor that they all can descend to}. For example, if there is a staircase from floor $3$ to floor $2$, then Sasha cannot invite residents from floors $2$ and $3$ to solve the task on floor $1$, as all residents can gather on a higher floor.

Sasha does not like to appear intrusive, so he will invite a resident from each floor to solve no more than one task. At the same time, he may choose not to invite residents from some floors to solve tasks.

Sasha has one more favorite task that he will not share with anyone except you. But for him to tell you about it, you need to help him count the number of different ways to invite residents to solve tasks with him, ensuring that all restrictions are met. Two ways are considered different if at least one task is solved by a different set of residents.