There is a tree T with N vertices, numbered 1 through N. For each 1 ≤ i ≤ N - 1, the i-th edge connects vertices a_i and b_i.

Snuke is constructing a directed graph T' by arbitrarily assigning direction to each edge in T. (There are 2^{N - 1} different ways to construct T'.)

For a fixed T', we will define d(s,\ t) for each 1 ≤ s,\ t ≤ N, as follows:

* d(s,\ t) = (The number of edges that must be traversed against the assigned direction when traveling from vertex s to vertex t)



In particular, d(s,\ s) = 0 for each 1 ≤ s ≤ N. Also note that, in general, d(s,\ t) ≠ d(t,\ s).

We will further define D as the following:

3d2f3f88e8fa23f065c04cd175c14ebf.png

Snuke is constructing T' so that D will be the minimum possible value. How many different ways are there to construct T' so that D will be the minimum possible value, modulo 10^9 + 7?

Constraints

* 2 ≤ N ≤ 1000
* 1 ≤ a_i,\ b_i ≤ N
* The given graph is a tree.

Input

The input is given from Standard Input in the following format:


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


Output

Print the number of the different ways to construct T' so that D will be the minimum possible value, modulo 10^9 + 7.

Examples

Input

4
1 2
1 3
1 4


Output

2


Input

4
1 2
2 3
3 4


Output

6


Input

6
1 2
1 3
1 4
2 5
2 6


Output

14


Input

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


Output

102
using System;
using System.Text;
using System.Collections.Generic;
class Solve{
    int N;
    List<int>[] T;
    bool[] b;
    int m;
    int mv;
    int[] m1;
    int[] m2;
    long[,] DP;
    public Solve(){}
    StringBuilder sb;
    public static int Main(){
        new Solve().Run();
        return 0;
    }
    void Run(){
        sb = new StringBuilder();
        Calc();
        Console.Write(sb.ToString());
    }
    void Calc(){
        N = int.Parse(Console.ReadLine());
        T = new List<int>[N];
        for(int i=0;i<N;i++){
            T[i] = new List<int>();
        }
        for(int i=0;i<N-1;i++){
            string[] str = Console.ReadLine().Split(' ');
            int a = int.Parse(str[0])-1;
            int b = int.Parse(str[1])-1;
            T[a].Add(b);
            T[b].Add(a);
        }
        b = new bool[N];
        m = N;
        mv = 0;
        m1 = new int[N];
        m2 = new int[N];
        GetCenter(0);
        b = new bool[N];
        GetCenter(0,0);
        b = new bool[N];
        DP = new long[N,N];
        m1 = new int[N];
        m2 = new int[N];
        GetCenter(mv);
        b = new bool[N];
        long sum = 0;
        int l = 0;
        dfs(mv);
        Console.WriteLine(mv);
        Debug.Print(DP);
        for(int i=0;i<T[mv].Count;i++){
            int t = T[mv][i];
            if(m1[t]+1 == m1[mv]){
                l = t;
                break;
            }
        }
        for(int x=0;x<=m1[mv];x++){
            long count = x == 0 ? 1 : (x == 1 ? 1 + DP[l,x] - DP[l,x-1] : DP[l,x] - DP[l,x-2]);
            for(int i=0;i<T[mv].Count;i++){
                int t = T[mv][i];
                if(t != l){
                    int d = m1[t]+1; 
                    long w = x == 0 ? 1 : (DP[t,x]-(x+d-m-1 >= 0 ? DP[t,x+d-m-1] : 0)) + (DP[t,x-1]-(x+d-m-2 >= 0 ? DP[t,x+d-m-2] : 0));
                    count = count*w%Define.mod;
                }
            }
            Console.WriteLine(count);
            sum = (sum+count)%Define.mod;
        }
        sb.Append(sum+"\n");
    }
    void dfs(int v){
        b[v] = true;
        for(int i=0;i<N;i++){
            DP[v,i] = 1;
        }
        for(int i=0;i<T[v].Count;i++){
            int t = T[v][i];
            if(!b[t]){
                dfs(t);
                for(int j=1;j<N;j++){
                    DP[v,j] *= DP[t,j] + DP[t,j-1];
                    DP[v,j] %= Define.mod;
                }
            }
        }
    }
    int GetCenter(int v){
        b[v] = true;
        for(int i=0;i<T[v].Count;i++){
            int t = T[v][i];
            if(!b[t]){
                int x = GetCenter(t);
                if(m1[v] <= x+1){
                    m2[v] = m1[v];
                    m1[v] = x+1; 
                }
                else if(m2[v] <= x+1){
                    m2[v] = x+1;
                }
            }
        }
        return m1[v];
    }
    void GetCenter(int v,int l){
        b[v] = true;
        if(l >= m1[v]){
            for(int i=0;i<T[v].Count;i++){
                int t = T[v][i];
                if(!b[t]){
                    GetCenter(t,l+1);
                }
            }
            if(m > l){
                m = l;
                mv = v;
            }
        }
        else{
            for(int i=0;i<T[v].Count;i++){
                int t = T[v][i];
                if(!b[t]){
                    if(m1[t]+1 == m1[v]){
                        GetCenter(t,Math.Max(l+1,m2[v]+1));
                    }
                    else{
                        GetCenter(t,m1[v]+1);
                    }
                }
            }
            if(m > m1[v]){
                m = m1[v];
                mv = v;
            }
        }
    }
}
public class Tree{
    List<int>[] T;
    bool[] b;
    int N;
    int temp1;
    int temp2;
    public int center1;
    public int center2;
    int diamater;
    public Tree(List<int>[] G){
        T = G;
        N = G.Length;
    } 
    void calcLongestPath(int v){
        b = new bool[N];
        temp1 = 0;
        temp2 = 0;
        dfs1(v,l);
    }
    public int LongestPathDistance(int v){
        calcLongestPath(v);
        return temp1;
    }
    public int LongestPath(int v){
        calcLongestPath(v);
        return temp2;
    }
    public void Diamater(){
        int x1 = LongestPath(0);
        int x2 = LongestPath(x1);
        diamater = temp1;
    }
    public void Center(){
        int x1 = LongestPath(0);
        int x2 = LongestPath(x1);
        diamater = temp1;
        if(diamater % 2 == 0){
            center1 = Search(x1,x2,diamater/2);
            center2 = -1;
        }
        else{
            center1 = Search(x1,x2,diamater/2);
            center2 = Search(x1,x2,diamater/2+1);
        }
    }
    public int Search(int s,int t,int l){
        b = new bool[N];
        dfs2(s,t,0,l);
        return temp1;
    }
    void dfs1(int v,int l){
        b[v] = true;
        for(int i=0;i<T[v].Count;i++){
            int t = T[v][i];
            if(!b[t]){
                dfs(t,l+1);
            }
        }
        if(l >= temp1){
            temp1 = l;
            temp2 = v;
        }
    }
    bool dfs2(int v,int o,int l,int d){
        b[v] = true;
        bool x = v == o;
        for(int i=0;i<T[v].Count;i++){
            int t = T[v][i];
            if(!b[t]){
                x |= dfs(t,o,l+1,d);
            }
        }
        if(x && l == d){
            temp1 = v;
        }
        return true;
    }
}
public static class Define{
    public const long mod = 1000000007;
}