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;

typedef long long LL;
#define N 300000

const LL mod=998244353;
LL n,f[N][3][3],g[3][3],d[N],m,mx,rt,fa[N];
vector<LL> e[N];

void dfs(LL u,LL dist){
	if (dist>mx){mx=dist; rt=u;}
	for (LL v:e[u])
		if (v!=fa[u]){
			fa[v]=u;
			dfs(v,dist+1);
		}
}

LL inv(LL x){return x==1?1:(mod-mod/x)*inv(mod%x)%mod;}

void upd(LL &x,LL y){x=(x+y)%mod;}

void dp(LL u,LL dist){
	if (dist==m/2) f[u][1][1]=1;
	else f[u][0][0]=1;
	for (LL v:e[u])
		if (v!=fa[u]){
			fa[v]=u;
			dp(v,dist+1);
			memset(g,0,sizeof g);
			for (LL i1:{0,1,2}) for (LL i2:{0,1,2}) for (LL j1:{0,1,2}) for (LL j2:{0,1,2})
				for (LL k:{0,1,2}){
					LL t1=j1*(k==1),t2=j2*(k==2);
					t1=min(2LL,i1+t1); t2=min(2LL,i2+t2);
					upd(g[t1][t2],f[u][i1][i2]*f[v][j1][j2]);
				}
			memcpy(f[u],g,sizeof f[u]);
		}
}

int main(){
	scanf("%lld",&n);
	for (LL i=1;i<n;++i){
		LL x,y; scanf("%lld%lld",&x,&y);
		e[x].push_back(y);
		e[y].push_back(x);
	}
	dfs(1,1);
	memset(fa,0,sizeof fa); mx=0;
	dfs(rt,1);
	for (LL i=rt;i;i=fa[i]) d[++m]=i;
	memset(fa,0,sizeof fa);
	if (m&1){
		LL p=d[m/2+1];
		dp(p,0);
		printf("%lld\n",f[p][1][1]*inv(2)%mod);
	}
	else{
		LL p1=d[m/2],p2=d[m/2+1];
		fa[p1]=p2; fa[p2]=p1;
		dp(p1,1); dp(p2,1);
		printf("%lld\n",(f[p1][1][0]+f[p1][1][1]+f[p1][1][2])*(f[p2][1][0]+f[p2][1][1]+f[p2][1][2])%mod);
	}
	
	return 0;
}