题目描述

“结束了。”小猫眼睁睁地看着右上角的时间倒数到 00:00:00。成绩表上只留下灰色的 −111。

这场 CodeForces 成为了小猫的心理阴影，所以他今天要滥用出题人的权力，将这一不美好的回忆强加于你。

现在你被迫解决根据小猫看错的题意出的题：有一棵 $n$ 个点的有根树，点的标号为 $1, 2, . . . , n$, $r$ 为树的根。现在有一个排列，满足若 $u$ 是 $v$ 的父结点，则 $u$ 排在 $v$ 之前。求所有如此的排列的逆序数平均值。

对 $10^9 + 7$ 取模，具体地，若答案为分数 $p/q$, 则输出 $x\in [0, 10^9 + 7)$ 使得 $qx\equiv p\pmod {10^9 + 7}$。

输入格式

第一行两个正整数 $n, r$, 分别表示点数和根的编号。保证 $1 ≤ r ≤ n$。

接下来 $n − 1$ 行每行两个正整数 $u, v$, 表示一条边的两端的编号。保证输入的所有边构成一棵树。

输出格式

一行一个正整数表示逆序数平均值，对 $10^9 + 7$ 取模的结果。

样例 #1

样例输入 #1

5 3
1 2
1 3
2 4
3 5

样例输出 #1

500000007

提示

样例解释

3 5 1 2 4：$5$ 对逆序

3 1 5 2 4：$4$ 对逆序

3 1 2 5 4：$3$ 对逆序

3 1 2 4 5：$2$ 对逆序

平均： $7/2\equiv 500000007 \pmod {10^9 + 7}$

数据范围

对于 $20\%$ 数据，$n ≤ 9$;

对于 $50\%$ 数据，$n ≤ 50$;

对于 $100\%$ 数据，$n ≤ 4096$。