Problem Description

There is a tree $ T $ with $ N $ vertices. The vertices are numbered from $ 1 $ to $ N $. For each $1 \leq i \leq N - 1$, the $ i $-th edge connects vertex $ a_i $ and vertex $ b_i $.

Snuke is trying to direct all edges of $ T $ in any direction he likes to create a directed graph $ T' $. (There are $ 2^{N - 1} $ possible $ T' $.)

When a $ T' $ is fixed, for each $1 \leq s, t \leq N$, $ d(s, t) $ is defined as follows:

• $ d(s, t) = $ (the number of edges that must be traversed against their direction when moving from vertex $ s $ to vertex $ t $ along the path in $ T' $)

In particular, for each $1 \leq s \leq N$, $ d(s, s) = 0 $. Note that in general, $d(s, t) \neq d(t, s)$.

Furthermore, $ D $ is defined as follows:

Snuke is trying to create $ T' $ such that $ D $ is minimized. How many possible $ T' $ can achieve the minimum value of $ D $? Find the answer modulo $ 10^9 + 7 $.

Input Format

The input is given from the standard input in the following format:

$ N $ $ a_1 $ $ b_1 $ $ a_2 $ $ b_2 $ $ : $ $ a_{N - 1} $ $ b_{N - 1} $

Output Format

Output the number of possible $ T' $ that achieve the minimum value of $ D $, modulo $ 10^9 + 7 $.

Sample Input and Output

Sample Input #1

4
1 2
1 3
1 4

Sample Output #1

2

Sample Input #2

4
1 2
2 3
3 4

Sample Output #2

6

Sample Input #3

6
1 2
1 3
1 4
2 5
2 6

Sample Output #3

14

Sample Input #4

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

Sample Output #4

102

Notes/Hints

Constraints

• $2 \leq N \leq 1000$
• $1 \leq a_i, b_i \leq N$
• The input graph is a tree.

Sample Explanation 1

The minimum value of $ D $ is $ 1 $. There are $ 2 $ possible $ T' $ that achieve the minimum value of $ D $.

Sample Explanation 2

The minimum value of $ D $ is $ 2 $. There are $ 6 $ possible $ T' $ that achieve the minimum value of $ D $.

见题面 Input 部分

见题面 Output 部分