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
#include<cstdio>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(i=a;i<=b;i++)
using namespace std;
const int N=1010,zo=1005;
const int mod=1e9+7;
int fa[N],son[N],dep[N];int ond[N];
int a[N],m;int d[N];int dia,u,v;int n;
struct node{
	int to,next;
};node edge[N*2];
int graph[N],tot;
void addedge(int i,int x,int y){
	edge[i].to=y;edge[i].next=graph[x];graph[x]=i;
}

struct case1{
	int dp[N][2*N];
	void dfs(int x,int pre){
		int i,y;
		for(i=graph[x];i;i=edge[i].next){
			y=edge[i].to;
			if(y==pre)	continue;
			dep[y]=dep[x]+1;dfs(y,x);
		}
	}
	void DP(int x,int pre){
		int i,j,y;int delta=dia/2-dep[x];
		rep(i,zo-delta,zo+delta)	dp[x][i]=1;
		for(i=graph[x];i;i=edge[i].next){
			y=edge[i].to;
			if(y==pre)	continue;
			DP(y,x);
			rep(j,zo-delta,zo+delta) dp[x][j]=1ll*dp[x][j]*(dp[y][j-1]+dp[y][j+1])%mod;
					
		}
	}			
	void solve(){
		/*dp[a[1]][zo]=1;mid=ca/2+1;
		rep(i,1,ca){
			x=a[i];
			for(j=graph[x];j;j=edge[j].next){
				y=edge[j].to;if(ond[y])	continue;
				DP(y);
			}
		}	
		rep(i,2,n){
			x=a[i];y=a[i-1];
			rep(j,1,m)	dp[x][j]=(dp[y][j-1]+dp[y][j+1])%mod;
			rep(j,1,m)	if(dp[x][j]){
				for(k=graph[x];k;k=edge[k].next){
					y=edge[k].to;if(ond[y])	continue;
				}
			}
		}*/
		dep[a[dia/2+1]]=0;dfs(a[dia/2+1],0);
		DP(a[1],0);
		printf("%d\n",dp[a[1]][zo]);
	}
};case1 even;

struct case2{
	int dp[N][2*N][3];int g[2*N][3];
	void dfs(int x,int pre){
		int i,y;
		for(i=graph[x];i;i=edge[i].next){
			y=edge[i].to;
			if(y==pre)	continue;
			dep[y]=dep[x]+1;dfs(y,x);
		}
	}
	int lab1(int x,int y){
		if(x<zo+1)	return 0;
		if(x-zo-1+y<dia/2)	return 0;
		if(x-zo-1+y==dia/2)	return 1;
		else return 2;
	}
	void DP1(int x,int pre){
		int i,j,k,l,y;int delta=dia/2+1-dep[x];
		rep(i,zo+1-delta,zo+1+delta)	dp[x][i][lab1(i,dep[x])]=1;
		for(i=graph[x];i;i=edge[i].next){
			y=edge[i].to;
			if(y==pre||ond[y])	continue;
			DP1(y,x);
			rep(j,zo+1-delta,zo+1+delta) rep(k,0,2) g[j][k]=0;
			rep(j,zo+1-delta,zo+1+delta) rep(k,0,2) if(dp[x][j][k])	rep(l,0,2){
				g[j][max(k,l)]=(g[j][max(k,l)]+1ll*dp[x][j][k]*(dp[y][j+1][l]+dp[y][j-1][l]))%mod;
			}
			rep(j,zo+1-delta,zo+1+delta) rep(k,0,2) dp[x][j][k]=g[j][k];
		}
	}	
	int lab2(int x,int y){
		if(x>zo)	return 0;
		if(-x+zo+y<dia/2)	return 0;
		if(-x+zo+y==dia/2)	return 1;
		else return 2;
	}
	void DP2(int x,int pre){
		int i,j,k,y;int delta=dia/2+1-dep[x];
		rep(i,zo-delta,zo+delta) rep(j,0,2)	if(j+lab2(i,dep[x])<3)	dp[x][i][j]=1;
		for(i=graph[x];i;i=edge[i].next){
			y=edge[i].to;
			if(y==pre||ond[y])	continue;
			DP2(y,x);
			rep(j,zo-delta,zo+delta) rep(k,0,2){
				dp[x][j][k]=1ll*dp[x][j][k]*(dp[y][j+1][k]+dp[y][j-1][k])%mod;
			}
		}
	}
	void solve(){
		int i,j,k,l;
		dep[a[m/2+1]]=0;dep[a[m/2]]=0;
		dfs(a[m/2],a[m/2+1]);dfs(a[m/2+1],a[m/2]);
		dp[a[1]][zo][0]=1;
		rep(i,2,m/2)	DP1(a[i],0);
		rep(i,1,m/2-1){
			memset(g,0,sizeof(g));
			rep(j,zo-n,zo+n) rep(k,0,2) if(dp[a[i+1]][j][k]) rep(l,0,2){
				g[j][max(k,l)]=(g[j][max(k,l)]+1ll*dp[a[i+1]][j][k]*(dp[a[i]][j+1][l]+dp[a[i]][j-1][l]))%mod;
			}
			rep(j,zo-n,zo+n) rep(k,0,2)	dp[a[i+1]][j][k]=g[j][k];
		}
		rep(i,m/2+1,m)	DP2(a[i],0);
		rep(i,m/2+1,m) rep(j,zo-n,zo+n) rep(k,0,2) if(dp[a[i]][j][k]){
			dp[a[i]][j][k]=1ll*dp[a[i]][j][k]*(dp[a[i-1]][j+1][k]+dp[a[i-1]][j-1][k])%mod;
		}
		int ans=0;
		rep(i,0,2)	ans=(ans+dp[a[m]][zo+1][i])%mod;
		ans=1ll*ans*2%mod;
		printf("%d\n",ans);
	}
};case2 odd;
				

void find_dia(int x){
	int i,y;d[x]=x;int k1=x,k2=x;
	for(i=graph[x];i;i=edge[i].next){
		y=edge[i].to;
		if(y==fa[x])	continue;
		fa[y]=x;dep[y]=dep[x]+1;
		find_dia(y);
		if(dep[d[y]]>dep[k1])	{k2=k1;k1=d[y];}
		else if(dep[d[y]]>dep[k2])	{k2=d[y];}
	}
	if(dep[k1]+dep[k2]-2*dep[x]>dia){dia=dep[k1]+dep[k2]-2*dep[x];u=k1;v=k2;}
	d[x]=k1;
}

void dfs(int x){
	int i,y;
	for(i=graph[x];i;i=edge[i].next){
		y=edge[i].to;
		if(y==fa[x])	continue;
		fa[y]=x;dfs(y);son[x]++;
	}
}	
				
int main(){
	//freopen("a.in","r",stdin);
	//freopen("a.out","w",stdout);
	int i,j,k,x,y,w;
	scanf("%d",&n);
	rep(i,1,n-1){
		scanf("%d%d",&x,&y);
		tot++;addedge(tot,x,y);
		tot++;addedge(tot,y,x);
	}
	find_dia(1);
	fa[u]=0;dfs(u);
	for(x=v;x;x=fa[x]){a[++m]=x;ond[x]=1;}
	reverse(a+1,a+1+m);
	if(!(dia&1))	even.solve();
	else odd.solve();
	//else solve1();
	//printf("%d\n",ans);
}
		
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	