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;
const int N=2e5+5,mo=998244353,inv=499122177;
struct Edge{
	int next,to;
}edge[N*2];
int fi[N],se,rt,mx,fa[N],f[N][3][3],tmp[3][3];
//f[i][j][k]±íÊ¾i×ÓÊ÷ÖÐÓÐ´ïµ½d==-m/2ºÍm/2Éî¶ÈµÄ½Úµã¸öÊý(2´ú±í¶à¸ö
//it's easy to prove f[i][j][k]=f[i][k][j]
inline void add_edge(int u,int v){edge[++se].next=fi[u],fi[u]=se,edge[se].to=v;}
inline void add(int u,int v){add_edge(u,v),add_edge(v,u);}
void dfs(int x,int d){
	if(d>mx)mx=d,rt=x;
	for(int i=fi[x];i;i=edge[i].next){
		int v=edge[i].to;if(v==fa[x])continue;
		fa[v]=x,dfs(v,d+1);
	}
}
void dp(int x,int d,int fa){
	if(d==mx/2)f[x][1][1]=1;
	else f[x][0][0]=1;
	for(int i=fi[x];i;i=edge[i].next){
		int v=edge[i].to;if(v==fa)continue;
		dp(v,d+1,x);
		memset(tmp,0,sizeof(tmp));
		for(int t1:{0,1,2})for(int t2:{0,1,2})for(int s1:{0,1,2})for(int s2:{0,1,2}){
			for(int k:{0,1,2}){//0 indicate d[u]==d[v],1 indicate d[v]==d[u]-1,2 indicate d[v]==d[u]+1
				int w1=min(2,t1+s1*(k==1)),w2=min(2,t2+s2*(k==2));
				(tmp[w1][w2]+=1ll*f[x][t1][t2]*f[v][s1][s2]%mo)%=mo;
			}
		}
		memcpy(f[x],tmp,sizeof(tmp));
	}
}
int main(){
	int n,u,v;scanf("%d",&n);
	for(int i=1;i<n;i++)scanf("%d%d",&u,&v),add(u,v);
	dfs(1,0);
	mx=fa[rt]=0,dfs(rt,0);
	for(int i=0;i<mx/2;i++)rt=fa[rt];
	if(mx&1){
		u=rt,v=fa[rt];
		dp(u,0,v),dp(v,0,u);
		printf("%d\n",(1ll*f[u][1][0]+f[u][1][1]+f[u][1][2])*(1ll*f[v][1][0]+f[v][1][1]+f[v][1][2])%mo);
	}
	else{
		dp(rt,0,0);
		printf("%d\n",1ll*f[rt][1][1]*inv%mo);
	}
	return 0;
}