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 <algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<ctime>
#include<set>
#include<queue>
#define sqr(x) ((x)*(x))
#define fz1(i,n) for ((i)=1;(i)<=(n);++(i))
#define fd1(i,n) for ((i)=(n);(i)>=1;--(i))
#define fz0g(i,n) for ((i)=0;(i)<=(n);++(i))
#define fd0g(i,n) for ((i)=(n);(i)>=0;--(i))
#define fz0k(i,n) for ((i)=0;(i)<(n);++(i))
#define fd0k(i,n) for ((i)=(long long)((n)-1);(i)>=0;--(i))
#define fz(i,x,y) for ((i)=(x);(i)<=(y);++(i))
#define fd(i,y,x) for ((i)=(y);(i)>=(x);--(i))
#define ff(c,itr) for (__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
#define rdst(st,len){static char ss[len];scanf(" %s",ss);(st)=ss;}
using namespace std;
const int mod=998244353;
int n,m,i,j,a[300005],dep[300005],pre[300005],dp[300005][3][3],f[3][3],mx,mxd,rt;
vector<int> bi[300005],seq;
void dfs1(int x,int fa)
{
	if(dep[x]>mx){
		mx=dep[x];
		mxd=x;
	}
	ff(bi[x],it){
		if(*it==fa) continue;
		dep[*it]=dep[x]+1;
		pre[*it]=x;
		dfs1(*it,x);
	}
}
void dfs2(int x,int fa)
{
	if(dep[x]==seq.size()/2) dp[x][1][1]=1; else dp[x][0][0]=1;
	ff(bi[x],it){
		if(*it==fa) continue;
		dep[*it]=dep[x]+1;
		dfs2(*it,x);
		memset(f,0,sizeof(f));
		int a,b,c,d,i;
		fz0k(a,3)fz0k(b,3){
			fz0k(c,3)fz0k(d,3){
				fz0k(i,3){
					int na=min(2,a+c*(i==1));
					int nb=min(2,b+d*(i==2));
					f[na][nb]=(f[na][nb]+1ll*dp[x][a][b]*dp[*it][c][d])%mod;
				}
			}
		}
		memcpy(dp[x],f,sizeof(f));
	}
}
int main()
{
	scanf("%d",&n);
	fz1(i,n-1){
		int x,y;
		scanf("%d%d",&x,&y);
		bi[x].push_back(y);
		bi[y].push_back(x);
	}
	mx=mxd=-1;
	dfs1(1,0);
	dep[mxd]=0;
	mx=-1;
	dfs1(rt=mxd,0);
	int x=mxd;
	while(x!=rt){
		seq.push_back(x);
		x=pre[x];
	}
	seq.push_back(x);
/*	ff(seq,it){
		cerr<<*it<<' ';
	}cerr<<endl;*/
	if(seq.size()&1){
		int x=seq[seq.size()/2];
		dep[x]=0;
		dfs2(x,0);
		printf("%lld\n",1ll*dp[x][1][1]*(mod+1)/2%mod);
	}
	else{
		int x=seq[seq.size()/2-1],y=seq[seq.size()/2];
		dep[x]=dep[y]=1;
		dfs2(x,y);dfs2(y,x);
		printf("%lld\n",(0ll+dp[x][1][0]+dp[x][1][1]+dp[x][1][2])*(0ll+dp[y][1][0]+dp[y][1][1]+dp[y][1][2])%mod);
	} 
	return 0;
}