#P17537. [PM13692] TwoEntrances

[PM13692] TwoEntrances

题目描述

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

房子有两个入口,分别直接通向房间 s1s_1 和 s2s_2。

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

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

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

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

输入格式

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

接下来 MM 行,每行输入两个整数 ai,bia_i,b_i,表示房间 aia_i 与 bib_i 之间有一条通道。

输出格式

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

数据范围

  • 2≤N≤30002\le N\le3000;
  • M=N−1M=N-1;
  • 0≤ai,bi<N0\le a_i,b_i<N;
  • 输入边构成一棵树;
  • 0≤s1,s2<N0\le s_1,s_2<N 且 s1≠s2s_1\ne s_2。

样例

3 0 1
0 1
1 2
2 3
4

说明

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