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<iostream>
#include<cstdio>
#include<vector>
using namespace std;
const int N=200005;
const int MOD=998244353;
int n;
vector<int>G[N];
int s,t;
int Max,p;
int dep[N];
int fa[N];
void dfs(int u,int father)
{
	fa[u]=father;
	dep[u]=dep[father]+1;
	if(dep[u]>Max) Max=dep[u],p=u;
	for(int v:G[u])
	{
		if(v==father) continue;
		dfs(v,u);
	}
	return;
}
vector<int>pos;
int len;
long long f[N][3][3];
long long g[3][3];
void DP(int u,int father,int d)
{
	if(d==len/2) f[u][1][1]=1;
	else f[u][0][0]=1;
	for(int v:G[u])
	{
		if(v==father) continue;
		DP(v,u,d+1);
		for(int i=0;i<=2;i++)
			for(int j=0;j<=2;j++)
				for(int x=0;x<=2;x++)
					for(int y=0;y<=2;y++)
						for(int k=-1;k<=1;k++)
						{
							int p=min(2,i+x*(k==-1)),q=min(2,j+y*(k==1));
							g[p][q]=(g[p][q]+f[u][i][j]*f[v][x][y]%MOD)%MOD;
						}
		for(int i=0;i<3;i++)
			for(int j=0;j<3;j++)
				f[u][i][j]=g[i][j],g[i][j]=0;
	}
	return;
}
long long ksm(long long a,long long b)
{
	long long res=1;
	while(b)
	{
		if(b&1) res=res*a%MOD;
		a=a*a%MOD,b>>=1;
	}
	return res;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<n;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		G[x].push_back(y);
		G[y].push_back(x);
	}
	dfs(1,0);
	s=p;
	Max=0;
	dfs(s,0);
	t=p;
	for(int u=t;u!=s;u=fa[u])
		pos.push_back(u);
	pos.push_back(s);
	len=pos.size()-1;
	if(len%2==0)
	{
		int x=pos[len/2];
		DP(x,0,0);
		printf("%lld",f[x][1][1]*ksm(2,MOD-2)%MOD);
	}
	else
	{
		int x=pos[(len-1)/2],y=pos[(len+1)/2];
		DP(x,y,0);
		DP(y,x,0);
		long long fx=(f[x][1][0]+f[x][1][1]+f[x][1][2])%MOD,fy=(f[y][0][1]+f[y][1][1]+f[y][2][1])%MOD;
		printf("%lld",fx*fy%MOD);
	}
	return 0;
}