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 rep(i,a,b) for(int i=(a);i<(b);++i)
#define per(i,a,b) for(int i=(b)-1;i>=(a);--i)
#define ll long long
#define lb(x) ((x)&(-x))
#define pii pair<int,int>
#define vi vector<int>
#define pb push_back
#define fi first
#define se second
#define de(x) cout<<x<<" x"<<endl
#define LCAFA rep(i,1,20)rep(j,1,n+1)fa[j][i]=fa[fa[j][i-1]][i-1]
#define all(x) x.begin(),x.end()
#define ls(x) x<<1
#define rs(x) x<<1|1
using namespace std;
const int N=2e5+9;
const ll mod=998244353;
int d[N],cnt,vis[N],stk[N];
vi g[N];
ll dp[N][3],temp[3];
ll add(ll x,ll y){
	return ((x+y)%mod+mod)%mod;
}
ll mul(ll x,ll y){
	return ((x*y)%mod+mod)%mod;
}
void dfs(int u,int f){
	for(auto v:g[u]){
		if(v==f)continue;
		d[v]=d[u]+1;
		dfs(v,u); 
	}
}
void dfs2(int u,int f){
	for(auto v:g[u]){
		if(v==f)continue;
		dfs2(v,u);
		if(vis[v])vis[u]=1;
	}
	if(vis[u])stk[++cnt]=u;
}
void sol(int u,int f){
	if(g[u].size()==1){
		if(vis[u])dp[u][0]=2,dp[u][1]=1;
		else dp[u][0]=3;
		return;
	}
	dp[u][0]=1;
	for(auto v:g[u]){
		if(v==f)continue;
		sol(v,u);
		rep(i,0,3)temp[i]=0;
		rep(i,0,3)rep(j,0,3)temp[min(2,i+j)]=add(temp[min(2,i+j)],mul(dp[u][i],dp[v][j]));
		rep(i,0,3)dp[u][i]=temp[i];
	//	cout<<v<<' '<<u<<" uv\n\n";
	//	cout<<dp[u][0]<<' '<<dp[u][1]<<' '<<dp[u][2]<<"checkdp\n";
	}
	dp[u][0]=add(dp[u][0],mul(2,dp[u][0]+dp[u][1]+dp[u][2])); 
}
int main(){
	int n;
	scanf("%d",&n);
	rep(i,1,n){
		int u,v;
		scanf("%d%d",&u,&v);
		g[u].pb(v),g[v].pb(u);
	}
	dfs(1,0);
	int p=1;
	rep(i,1,n+1)if(d[i]>d[p])p=i;
	d[p]=0;
	dfs(p,0);
	int e=1;
	rep(i,1,n+1)if(d[i]>d[e])e=i;
	vis[e]=1;
	dfs2(p,0);
	memset(vis,0,sizeof vis);
	if(cnt&1){
	//	cout<<"comein\n";
		int u=stk[cnt/2+1];d[u]=0;dfs(u,0);
		rep(i,1,n+1)if(d[i]==cnt/2)vis[i]=1;
		ll ans[3]={1,0,0};
		for(auto v:g[u]){
		//	cout<<v<<"  v\n";
			sol(v,u);
			dp[v][0]-=dp[v][1]+dp[v][2];
			ans[2]=add(mul(ans[2],dp[v][0]),mul(ans[1],dp[v][1]));
			ans[1]=add(mul(ans[1],dp[v][0]),mul(ans[0],dp[v][1]));
			ans[0]=mul(ans[0],dp[v][0]);
		//	cout<<dp[v][0]<<' '<<dp[v][1]<<' '<<dp[v][2]<<"dp\n";
		//	cout<<ans[0]<<' '<<ans[1]<<' '<<ans[2]<<"check\n";
		}
		printf("%lld",ans[2]);
	}
	else{
		int u=stk[cnt>>1],v=stk[cnt/2+1];
		d[u]=0;d[v]=0;
		dfs(u,v);dfs(v,u);
		rep(i,1,n+1)if(d[i]==cnt/2-1)vis[i]=1;
		sol(u,v);sol(v,u);
		ll ans=mul(dp[u][1],dp[v][1]);
		printf("%lld",ans);
	}
}