题目描述

Maki 的新房子有 $N$ 个房间，编号为 $0$ 到 $N-1$。房间之间有 $N-1$ 条双向通道，并且这些通道构成一棵树。

房子有两个入口，分别直接通向房间 $s_1$ 和 $s_2$。

Maki 有恰好 $N$ 件互不相同的家具，家具编号为 $0$ 到 $N-1$。Niko 会按照家具编号从小到大的顺序依次搬入，每个房间最终恰好放一件家具。

家具非常大：一旦某个房间已经放入家具，之后就不能再搬着其他家具穿过该房间。因此，将下一件家具放入房间 $x$ 当且仅当存在某个入口到 $x$ 的路径，并且该路径上的所有房间此时都还是空的。

Niko 会选择一种永远不会中途卡死的放置方式，直到所有房间都各有一件家具。

求最后家具与房间之间可能出现多少种不同的对应关系。答案对 $10^9+7$ 取模。

输入格式

第一行输入三个整数 $M,s_1,s_2$，其中 $M=N-1$。

接下来 $M$ 行，每行输入两个整数 $a_i,b_i$，表示房间 $a_i$ 与 $b_i$ 之间有一条通道。

输出格式

输出一个整数，表示合法最终摆放方案数对 $10^9+7$ 取模后的结果。

数据范围

• $2\le N\le3000$；
• $M=N-1$；
• $0\le a_i,b_i<N$；
• 输入边构成一棵树；
• $0\le s_1,s_2<N$ 且 $s_1\ne s_2$。

样例

3 0 1
0 1
1 2
2 3

4

说明

对于这条四个房间的链，四种可行的填房顺序分别为 $\{3,2,1,0\}$、$\{3,2,0,1\}$、$\{3,0,2,1\}$、$\{0,3,2,1\}$。