19387번 - Counting Orders 다국어

문제

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

제한

힌트

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