시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 0 0 0 0.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$.

예제 입력 1

6
1 1 1 2 3
2 3

예제 출력 1

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$.