TopCoder

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

66.7% (2/3)

Tags

Description

小風很喜歡數樹,他看到甚麼東西都想要算個數,特別是堅果樹,一邊數著堅果樹上的堅果一邊吃堅果是小風的休閒活動。而所謂的堅果樹與一般的樹最大的差別就是堅果樹的每個點都會有一些堅果果實。

現在小風拿到一棵 N 個點的堅果樹,並且他手上有編號分別為 1,2,,N 的堅果,他把這 N 顆堅果分別放到這顆堅果樹的 N 個點上,這樣的堅果樹就叫做一棵有序堅果樹。小風雖然很愛數樹,但他卻算不出來一共有幾棵不同構的有序堅果樹,不過這個問題其實很簡單,所以希望你能夠繼續當小風的好朋友,幫幫他算出可以得到幾棵不同構的有序堅果樹。

對於兩棵有序堅果樹,如果存在某個正整數 k ,在兩棵有序堅果樹中和堅果編號為 k 相鄰的堅果編號集合不同,我們就說兩棵這有序堅果樹是不同構的。

Input Format

輸入第一行只有一個正整數 N,代表這棵堅果樹一共有 N 個點。

接下來有 N1 行,每一行都有兩個正整數 x,y,代表堅果樹上的一條邊。

  • 1N2×105
  • 1x,yN

Output Format

對於每一組輸入,請輸出一個非負整數代表有多少個不同構的有序堅果樹,請輸出答案 mod109+7

Sample Input 1

4
1 2
2 3
2 4

Sample Output 1

4

Sample Input 2

5
1 2
2 3
2 4
1 5

Sample Output 2

60

Sample Input 3

9
1 2
2 3
2 4
2 5
5 6
6 7
6 8
6 9

Sample Output 3

5040

Hints

Problem Source

IOICamp 2020 Day5 pF

Subtasks

No. Testdata Range Constraints Score
1 0~2 範例測資 0
2 0~34 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 262144 65536 1 2
1 1000 262144 65536 1 2
2 1000 262144 65536 1 2
3 1000 262144 65536 2
4 1000 262144 65536 2
5 1000 262144 65536 2
6 1000 262144 65536 2
7 1000 262144 65536 2
8 1000 262144 65536 2
9 1000 262144 65536 2
10 1000 262144 65536 2
11 1000 262144 65536 2
12 1000 262144 65536 2
13 1000 262144 65536 2
14 1000 262144 65536 2
15 1000 262144 65536 2
16 1000 262144 65536 2
17 1000 262144 65536 2
18 1000 262144 65536 2
19 1000 262144 65536 2
20 1000 262144 65536 2
21 1000 262144 65536 2
22 1000 262144 65536 2
23 1000 262144 65536 2
24 1000 262144 65536 2
25 1000 262144 65536 2
26 1000 262144 65536 2
27 1000 262144 65536 2
28 1000 262144 65536 2
29 1000 262144 65536 2
30 1000 262144 65536 2
31 1000 262144 65536 2
32 1000 262144 65536 2
33 1000 262144 65536 2
34 1000 262144 65536 2