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<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<ctime>
#include<map>
#include<bitset>
#include<set>
#include<assert.h>
#define LL long long
#define mp(x,y) make_pair(x,y)
#define pll pair<long long,long long>
#define pii pair<int,int>
#define SZ(x) ((int)x.size())
using namespace std;
inline LL read()
{
	LL f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int stack[20];
template<typename T>inline void write(T x)
{
	if(x<0){putchar('-');x=-x;}
    if(!x){putchar('0');return;}
    int top=0;
    while(x)stack[++top]=x%10,x/=10;
    while(top)putchar(stack[top--]+'0');
}
template<typename T>inline void pr1(T x){write(x);putchar(' ');}
template<typename T>inline void pr2(T x){write(x);putchar('\n');}
template<typename T>inline void chkmin(T &x,T y){x=x<y?x:y;}
template<typename T>inline void chkmax(T &x,T y){x=x>y?x:y;}
const int MAXN=200005;
const int mod=998244353;
void ad(int &x,int y){x+=y;if(x>=mod)x-=mod;}
vector<int> nxt[MAXN];
void ins(int x,int y){nxt[x].emplace_back(y);}
int dis[MAXN],sta[MAXN],tp,n;
void dfs(int x,int fa){for(auto y:nxt[x])if(y^fa)dis[y]=dis[x]+1,dfs(y,x);}
bool getpath(int x,int fa,int ed)
{
	if(x==ed){sta[++tp]=x;return true;}
	for(auto y:nxt[x])if((y^fa)&&getpath(y,x,ed)){sta[++tp]=x;return true;}
	return false;
}
int f[MAXN][3];//存在几条不同子树与父亲差值没变且为mx的 
int trans[3];bool tag[MAXN];
void dp(int x,int fa)
{
	if(SZ(nxt[x])==1)
	{
		if(tag[x])f[x][1]=1,f[x][0]=2;
		else f[x][0]=3;return ;
	}f[x][0]=1;
	for(auto y:nxt[x])if(y^fa)dp(y,x);
	for(auto y:nxt[x])if(y^fa)
	{
		memset(trans,0,sizeof(trans));
		for(int i=0;i<3;i++)for(int j=0;j<3;j++)if(f[x][i]&&f[y][j])
			ad(trans[min(2,i+j)],1LL*f[x][i]*f[y][j]%mod);//+1
		for(int i=0;i<3;i++)f[x][i]=trans[i];
	}f[x][0]=(3LL*f[x][0]+2LL*(f[x][1]+f[x][2]))%mod;
}
int ans[3];
int main()
{
//	freopen("a.in","r",stdin);
//	freopen("a.out","w",stdout);
	n=read();
	for(int i=1;i<n;i++)
	{
		int x=read(),y=read();
		ins(x,y);ins(y,x);
	}dfs(1,0);int p=0,q=0;for(int i=1;i<=n;i++)if(dis[i]>dis[p])p=i;
	dis[p]=0;dfs(p,0);for(int i=1;i<=n;i++)if(dis[i]>dis[q])q=i;
	getpath(p,0,q);
	if(tp&1)
	{
		int u=sta[tp/2+1];dis[u]=0;dfs(u,0);
		for(int i=1;i<=n;i++)if(dis[i]==tp/2)tag[i]=1;
		ans[0]=1;
		for(auto y:nxt[u])
		{
			dp(y,u);int x0=(f[y][0]-(f[y][1]+f[y][2])%mod+mod)%mod,x1=f[y][1];
			ans[2]=(1LL*ans[2]*x0+1LL*ans[1]*x1)%mod;
			ans[1]=(1LL*ans[1]*x0+1LL*ans[0]*x1)%mod;
			ans[0]=1LL*ans[0]*x0%mod;
		}pr2(ans[2]);
	}
	else
	{
		int u=sta[tp/2],v=sta[tp/2+1];dis[u]=dis[v]=0;dfs(u,v);dfs(v,u);
		for(int i=1;i<=n;i++)if(dis[i]==(tp-1)/2)tag[i]=1;
		dp(u,v);dp(v,u);pr2(1LL*f[u][1]*f[v][1]%mod);
	}
	return 0;
}