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 mod=998244353,iv=(mod+1)/2;
int n,x,y,dist[222222],pre[222222],rt,cnt,dp[222222][4][4],len,f[4][4],G[4][4];
vector<int> g[222222];
int bfs(int s)
{
	queue<int> q;
	q.push(s);
	memset(dist,-1,sizeof(dist));
	dist[s]=0;
	while(!q.empty())
	{
		int x=q.front();q.pop();
		for (int i=0;i<g[x].size();i++)
		{
			int to=g[x][i];
			if (!~dist[to])
			{
				dist[to]=dist[x]+1;
				pre[to]=x;
				q.push(to);
			}
		}
	}
	int mxi=1;
	for (int i=2;i<=n;i++)
	{
		if (dist[i]>dist[mxi]) mxi=i;
	}
	return mxi;
}
void add(int &x,int y)
{
	x+=y;
	if (x>=mod) x-=mod;
}
void dfs(int i,int fa,int dep)
{
	if (dep==len)
	{
		dp[i][0][0]=dp[i][1][0]=dp[i][0][1]=1;
		return;
	}
	for (int j=0;j<g[i].size();j++)
	{
		int to=g[i][j];
		if (to==fa) continue;
		dfs(to,i,dep+1);
	}
	memset(f,0,sizeof(f));
	f[0][0]=1;
	for (int j=0;j<g[i].size();j++)
	{
		int to=g[i][j];
		if (to==fa) continue;
		memset(G,0,sizeof(G));
		for (int k=0;k<3;k++)
		{
			for (int h=0;h<3;h++)
			{
				for (int s=0;s<3;s++)
				{
					for (int t=0;t<3;t++)
					{
						add(G[min(k+s,2)][min(h+t,2)],1ll*f[k][h]*dp[to][s][t]%mod);
					}
				}
			}
		}
		memcpy(f,G,sizeof(G));
	}
	for (int j=0;j<3;j++)
	{
		for (int k=0;k<3;k++)
		{
			if (i!=rt)
			{
				add(dp[i][0][0],f[j][k]);
				add(dp[i][0][k],f[j][k]);
				add(dp[i][j][0],f[j][k]);
			}
			else 
			{
				add(dp[i][j][k],f[j][k]);
			}
		}
	}
}
int main()
{
	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);
	}
	x=bfs(1);
	y=bfs(x);
	if (dist[y]&1)
	{
		for (int i=y;i!=x;i=pre[i])
		{
			cnt++;
			if (cnt==(dist[y]+1)/2)
			{
				++n;
				rt=n;
				g[rt].push_back(i);
				g[rt].push_back(pre[i]);
				g[i].push_back(rt);
				g[pre[i]].push_back(rt);
				for (int j=0;j<g[i].size();j++)
				{
					if (g[i][j]==pre[i])
					{
						g[i].erase(g[i].begin()+j);
						break;
					}
				}
				for (int j=0;j<g[pre[i]].size();j++)
				{
					if (g[pre[i]][j]==i)
					{
						g[pre[i]].erase(g[pre[i]].begin()+j);
						break;
					}
				}
				len=(dist[y]+1)/2;
				break;
			}
		}
	}
	else
	{
		for (int i=y;i!=x;i=pre[i])
		{
			cnt++;
			if (cnt==dist[y]/2+1)
			{
				rt=i;
				len=dist[y]/2;
				break;
			}
		}
	}
	dfs(rt,0,0);
	printf("%d\n",1ll*dp[rt][1][1]*iv%mod);
	return 0;
}