TopCoder

Thumb maxresdefault
YenSean
Hello World!

User's AC Ratio

100.0% (14/14)

Submission's AC Ratio

76.3% (29/38)

Description

NPSC 魔法學院在今年正式成立囉!

從小就展現過人天賦的天才兒童殿壬,如今已成長茁壯並成為NPSC 魔法學院第一屆的學員了。一年級的課程對於殿壬來講根本就是小菜一碟,所以他跟著學院裡的教授一起衝鋒陷陣,研究最新穎的魔法技術:魔法鏈。

施展這種法術前,殿壬要先擁有一串由魔法寶石組成的魔力串珠。一串魔力串珠會由$N$ 顆魔法寶石組成,每顆魔法寶石都是相異的,用數字$1$ 到$N$ 表示。一串魔力串珠中還會有$N - 1$條線,每條線連接兩顆相異的魔法寶石,使得這$N$ 顆魔法寶石都會被串在一起(任兩顆魔法寶石都會透過一或多條線的串接而連接著)。

這項法術的施展,就是利用這串魔力串珠來製造一條魔法鏈。

製造魔法鏈時,若這串魔力串珠只有2 顆魔法寶石,就直接用魔力剪刀剪斷中間唯一的那條線,並且把這2 顆魔法寶石依任意順序放在魔法鏈的第1 跟第2 個位置。

否則,殿壬要挑選魔力串珠中的一條線並用魔力剪刀把它剪斷,使得在剪斷之後會形成一串有多顆魔法寶石的魔力串珠以及一顆獨立的魔法寶石(如果剪斷後不會變成這種結果,那麼殿壬就不能剪這條線),接著把這獨立的魔法寶石放在魔法鏈的下一個位置(剪第一刀時得到的魔法寶石放在第一個位置、剪第二刀時得到的魔法寶石放在第二個位置,依此類推),重複上述動作直到這串魔力串珠只剩下兩顆魔法寶石(中間由一條線連接著)時,殿壬就把最後這條線剪斷,並依他的選擇將最後的兩顆魔法寶石放在魔法鏈的第$N - 1$ 跟第$N$ 個位置。不難發現,就算是同樣的魔力串珠,也可以藉由不同的剪取順序而排出許多不同的魔法鏈,以下圖的魔力串珠(與範例一相同)為例,$2, 3, 5, 1, 4$、$5, 2, 4, 1, 3$ 跟$5, 2, 4, 3, 1$ 都是可能創造出的魔法鏈,不過$2, 1, 3, 4, 5$ 跟$2, 3, 4, 5, 1$ 就是不可能創造出來的魔法鏈。

現在給你一串魔法串珠,請你計算總共可以創造出多少種不同的魔法鏈。兩個魔法鏈只要任一個對應的位置不相等,就視為不同。因為答案可能很大,你的程式只需要輸出答案除以$10^ 9 + 7$的餘數即可。

Input Format

測試資料第一行包含一個正整數$N$,表示這串魔法串珠是由幾顆魔法寶石所組成。測試資
料接下來包含$N - 1$ 行,每行包含兩個正整數$a_i, b_i$,表示第$i $條線連接了魔法寶石$a_i$ 跟魔法寶石$b_i$。

  • $2 \leq N \leq 2000$
  • $1 \leq a_i, b_i \leq N$
  • 輸入的魔法串珠一定會讓$N$ 顆魔法寶石都被串在一起

Output Format

輸出一行,包含一個整數,表示該魔法串珠所能創造出的魔法鏈種類數除以$10^ 9 + 7 $的餘數。

Sample Input

Sample Input #1
5
1 2
1 3
1 4
4 5

Sample Input #2
2
1 2

Sample Input #3
4
1 2
2 3
3 4

Sample Output

Sample Output #1
28

Sample Output #2
2

Sample Output #3
8

Hints

Problem Source

2017 NPSC高中組決賽

Subtasks

For Testdata: 0 ~ 97, Score: 100
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 262144 262144
1 1000 262144 262144
2 1000 262144 262144
3 1000 262144 262144
4 1000 262144 262144
5 1000 262144 262144
6 1000 262144 262144
7 1000 262144 262144
8 1000 262144 262144
9 1000 262144 262144
10 1000 262144 262144
11 1000 262144 262144
12 1000 262144 262144
13 1000 262144 262144
14 1000 262144 262144
15 1000 262144 262144
16 1000 262144 262144
17 1000 262144 262144
18 1000 262144 262144
19 1000 262144 262144
20 1000 262144 262144
21 1000 262144 262144
22 1000 262144 262144
23 1000 262144 262144
24 1000 262144 262144
25 1000 262144 262144
26 1000 262144 262144
27 1000 262144 262144
28 1000 262144 262144
29 1000 262144 262144
30 1000 262144 262144
31 1000 262144 262144
32 1000 262144 262144
33 1000 262144 262144
34 1000 262144 262144
35 1000 262144 262144
36 1000 262144 262144
37 1000 262144 262144
38 1000 262144 262144
39 1000 262144 262144
40 1000 262144 262144
41 1000 262144 262144
42 1000 262144 262144
43 1000 262144 262144
44 1000 262144 262144
45 1000 262144 262144
46 1000 262144 262144
47 1000 262144 262144
48 1000 262144 262144
49 1000 262144 262144
50 1000 262144 262144
51 1000 262144 262144
52 1000 262144 262144
53 1000 262144 262144
54 1000 262144 262144
55 1000 262144 262144
56 1000 262144 262144
57 1000 262144 262144
58 1000 262144 262144
59 1000 262144 262144
60 1000 262144 262144
61 1000 262144 262144
62 1000 262144 262144
63 1000 262144 262144
64 1000 262144 262144
65 1000 262144 262144
66 1000 262144 262144
67 1000 262144 262144
68 1000 262144 262144
69 1000 262144 262144
70 1000 262144 262144
71 1000 262144 262144
72 1000 262144 262144
73 1000 262144 262144
74 1000 262144 262144
75 1000 262144 262144
76 1000 262144 262144
77 1000 262144 262144
78 1000 262144 262144
79 1000 262144 262144
80 1000 262144 262144
81 1000 262144 262144
82 1000 262144 262144
83 1000 262144 262144
84 1000 262144 262144
85 1000 262144 262144
86 1000 262144 262144
87 1000 262144 262144
88 1000 262144 262144
89 1000 262144 262144
90 1000 262144 262144
91 1000 262144 262144
92 1000 262144 262144
93 1000 262144 262144
94 1000 262144 262144
95 1000 262144 262144
96 1000 262144 262144
97 1000 262144 262144