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>
#define N 200100
using namespace std;
vector<int> g[N];
int to_leaf[N];
long long p3sz[N],nume[N][3];
const int Q=998244353;
int find_c(int u,int p){
	int mx[2]={u,u},ans=0;
	for(int i=0;i<g[u].size();i++){
		int v=g[u][i];
		if(v==p) continue;
		ans=max(ans,find_c(v,u));
		if(to_leaf[v]>to_leaf[mx[0]]){
			mx[1]=mx[0];
			mx[0]=v;
		}
		else if(to_leaf[v]>to_leaf[mx[1]]){
			mx[1]=v;
		}
	}
	ans=max(ans,to_leaf[mx[0]]+to_leaf[mx[1]]);
	to_leaf[u]=to_leaf[mx[0]]+1;
	return ans;
}
void build(int u,int p){
	to_leaf[u]=0;
	for(int i=0;i<g[u].size();i++){
		int v=g[u][i];
		if(v==p) continue;
		build(v,u);
		to_leaf[u]=max(to_leaf[u],to_leaf[v]+1);
	}
}
void solve(int u,int p){
	p3sz[u]=1;
	if(!to_leaf[u]){
		nume[u][1]=1;
		return;
	}
	nume[u][0]=1;
	for(int i=0;i<g[u].size();i++){
		int v=g[u][i];
		if(v==p) continue;
		solve(v,u);
		if(to_leaf[v]+1==to_leaf[u]){
			for(int j=2;j>=0;j--){
				if(p) nume[u][j]*=nume[v][0]+2*p3sz[v];
				else nume[u][j]*=2*nume[v][0]+p3sz[v];
				if(j) nume[u][j]+=nume[u][j-1]*nume[v][1];
				nume[u][j]%=Q;
			}
		}
		else{
			for(int j=0;j<3;j++){
				nume[u][j]=3*p3sz[v]*nume[u][j]%Q;
			}
		}
		p3sz[u]=3*p3sz[v]*p3sz[u]%Q;
	}
}
int main(){
	int n,x,y;
	scanf("%d",&n);
	for(int i=1;i<n;i++){
		scanf("%d%d",&x,&y);
		g[x].push_back(y);
		g[y].push_back(x);
	}
	int l,p=0,c=1;
	l=find_c(1,0);
	bool flag=true;
	while(flag){
		flag=false;
		for(int i=0;i<g[c].size();i++){
			if(g[c][i]!=p && to_leaf[g[c][i]]>(l+1)/2){
				p=c;
				c=g[c][i];
				flag=true;
				break;
			}
		}
	}
	//printf("diameter=%d\n",l);
	if(l&1){
		int d=-1;
		for(int i=0;i<g[c].size();i++){
			if(to_leaf[g[c][i]]==(l+1)/2){
				d=g[c][i];
				break;
			}
		}
		//printf("center: %d %d\n",c,d);
		assert(d>0);
		build(c,d);
		solve(c,d);
		build(d,c);
		solve(d,c);
		printf("%lld\n",1LL*nume[c][1]*nume[d][1]%Q);
	}
	else{
		//printf("center: %d\n",c);
		build(c,0);
		solve(c,0);
		printf("%lld\n",nume[c][2]);
	}
	return 0;
}