Problem: We have a tree G with N vertices numbered 1 to N. The i-th edge of G connects Vertex a_i and Vertex b_i.

Consider adding zero or more edges in G, and let H be the graph resulted.

Find the number of graphs H that satisfy the following conditions, modulo 998244353.

* H does not contain self-loops or multiple edges.
* The diameters of G and H are equal.
* For every pair of vertices in H that is not directly connected by an edge, the addition of an edge directly connecting them would reduce the diameter of the graph.

Constraints

* 3 \le N \le 2 \times 10^5
* 1 \le a_i, b_i \le N
* The given graph is a tree.

Input

Input is given from Standard Input in the following format:


N
a_1 b_1
\vdots
a_{N-1} b_{N-1}


Output

Print the answer.

Examples

Input

6
1 6
2 1
5 2
3 4
2 3


Output

3


Input

3
1 2
2 3


Output

1


Input

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


Output

27


Input

19
2 4
15 8
1 16
1 3
12 19
1 18
7 11
11 15
12 9
1 6
7 14
18 2
13 12
13 5
16 13
7 1
11 10
7 17


Output

78732

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=200000+5,mod=998244353;
int ksm(int b,int n){
	int res=1;
	while(n){
		if(n&1) res=res*b%mod;
		b=b*b%mod; n>>=1;
	}
	return res;
}
int add(int x,int y){
	return (x+y)%mod;
}
int mul(int x,int y){
	return x*y%mod;
}
vector<int> e[N];
int n,dis[N],pre[N];
int dp[N][3][3];
int bfs(int st){
	queue<int> q;
	int res=0;
	for(int i=1;i<=n;++i)
		dis[i]=0;
	dis[st]=1; pre[st]=0; q.push(st);
	while(!q.empty()){
		int u=q.front();q.pop();
		if(dis[u]>dis[res]) res=u;
		//cout<<st<<" "<<u<<" "<<dis[u]<<" "<<res<<endl;
		for(int i=0;i<e[u].size();++i)
			if(dis[e[u][i]]==0) q.push(e[u][i]),dis[e[u][i]]=dis[u]+1,pre[e[u][i]]=u;
	}
	return res;
}
int L,tmp[3][3];
void dfs(int u,int fath,int dep){
	//cout<<u<<" "<<fath<<" "<<dep<<endl;
	if(dep==L/2) dp[u][1][1]=1;
	else dp[u][0][0]=1;
	for(int i=0;i<e[u].size();++i){
		int v=e[u][i];
		if(v==fath) continue;
		dfs(v,u,dep+1);
		for(int x=0;x<=2;++x)
			for(int y=0;y<=2;++y)
				tmp[x][y]=0;
		for(int x=0;x<=2;++x)
			for(int y=0;y<=2;++y)
				for(int a=0;a<=2;++a)
					for(int b=0;b<=2;++b)
						for(int type=0;type<=2;++type){
							int p=min(x+(type==1)*a,2ll),q=min(y+(type==2)*b,2ll);
							tmp[p][q]=add(tmp[p][q],mul(dp[u][x][y],dp[v][a][b]));
						}
		for(int x=0;x<=2;++x)
			for(int y=0;y<=2;++y)
				dp[u][x][y]=tmp[x][y];
	}
	//for(int x=0;x<=2;++x)
	//	for(int y=0;y<=2;++y)
		//	cout<<u<<" "<<x<<" "<<y<<" "<<dp[u][x][y]<<endl;
}
int c[N],tot;
void solve(){
	int from=bfs(1),to=bfs(from);
	tot=0;while(to) c[++tot]=to,to=pre[to];
	L=tot;
	if(tot&1){
		from=c[(tot+1)/2];
		dfs(from,0,0);
		cout<<mul(dp[from][1][1],ksm(2,mod-2));
		return;
	}
	else{
		from=c[tot/2],to=c[(tot+2)/2];
	//	cout<<from<<" "<<to<<" "<<tot<<endl;
		dfs(from,to,1);
		int x=0,y=0;
		for(int i=0;i<=2;++i)
			x=add(x,dp[from][i][1]);
		dfs(to,from,1);
		for(int i=0;i<=2;++i)
			y=add(y,dp[to][1][i]);
		cout<<mul(x,y);
		return;
	}
}
signed main(){
	int ans=0,u,v;
	cin>>n;
	for(int i=1;i<n;++i){
		cin>>u>>v;
		e[u].push_back(v);
		e[v].push_back(u);
	}
	solve();
	return 0;
}