P9663 [ICPC 2021 Macao R] Permutation on Tree

Given a tree with $n$ vertices where vertex $r$ is the root, we say a permutation $p_1, p_2, \cdots, p_n$ of $n$ is good if it satisfies the following constraint: - Let $a_x$ be the index of $x$ in the permutation (That is, $p_{a_x} = x$). For all $1 \le u, v \le n$, if vertex $u$ is an ancestor of vertex $v$ in the tree, then $a_u < a_v$. Define the score of a permutation to be $\sum\limits_{i=1}^{n-1} |p_i - p_{i+1}|$ where $|x|$ is the absolute value of $x$. Calculate the sum of scores of all different good permutations.

There is only one test case in each test file. The first line contains two integers $n$ and $r$ ($2 \le n \le 200$, $1 \le r \le n$) indicating the size of the tree and the root. For the following $(n - 1)$ lines, the $i$-th line contains two integers $u_i$ and $v_i$ ($1 \le u_i, v_i \le n$) indicating an edge connecting vertex $u_i$ and $v_i$ in the tree.

For each test case output one line containing one integer indicating the sum of scores of all different good permutations. As the answer may be large, output the answer modulo $(10^9 + 7)$.

For the first sample test case, there are three good permutations: $\{2, 1, 3, 4\}$, $\{2, 1, 4, 3\}$ and $\{2, 3, 1, 4\}$. Their scores are $4$, $5$ and $6$ respectively so the answer is $4 + 5 + 6 = 15$. For the second sample test case, there is only one good permutation: $\{1, 2, 3\}$. It's score is $2$.