| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 512 MB | 4 | 3 | 3 | 75.000% |
You are given a rooted tree on $n$ vertices numbered from $1$ to $n$. The root of the tree is vertex $1$, and for each vertex $i$ ($i \geq 2$), its parent is vertex $p_i$.
Consider a permutation $q_i$ ($1 \le i \le n$). We will call this permutation proper if, for any vertex $v$, all its descendants are located to the right of the position of $v$ in permutation $q$.
You are asked to find the number of proper permutations $q_i$ such that $q_k = v$, taken modulo $10^9 + 7$.
The first line of the input contains a single integer $n$ ($1 \leq n \leq 5000$), the number of vertices in the tree.
The second line contains $n-1$ integers $p_2, p_3, \ldots, p_n$ ($1 \leq p_i < i$), the parents of all vertices in the tree except the root. In particular, when $n = 1$, the second line is present but empty.
The last line contains two integers $v$ and $k$ ($1 \le v, k \le n$).
Output one integer: the remainder of the number of proper permutations $q_i$ with $q_k = v$ modulo $10^9 + 7$.
6 1 1 1 2 3 2 3
9
The valid proper permutations for the sample case are:
$1 3 2 4 5 6$, $1 3 2 4 6 5$, $1 3 2 5 4 6$, $1 3 2 5 6 4$, $1 3 2 6 4 5$, $1 3 2 6 5 4$, $1 4 2 3 5 6$, $1 4 2 3 6 5$, $1 4 2 5 3 6$.