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<cmath>
#include<cstdlib>
#include<algorithm>
#include<vector>
#define ll long long
#define mod 998244353
#define maxn 200010
inline ll read()
{
	ll x=0; char c=getchar(),f=1;
	for(;c<'0'||'9'<c;c=getchar())if(c=='-')f=-1;
	for(;'0'<=c&&c<='9';c=getchar())x=x*10+c-'0';
	return x*f;
}
inline void write(ll x)
{
	static int buf[20],len; len=0;
	if(x<0)x=-x,putchar('-');
	for(;x;x/=10)buf[len++]=x%10;
	if(!len)putchar('0');
	else while(len)putchar(buf[--len]+'0');
}
inline void writeln(ll x){write(x); putchar('\n');}
inline void writesp(ll x){write(x); putchar(' ');}
const int inv2=(mod+1)/2;
std::vector<int>nxt[maxn];
int dist1[maxn],dist2[maxn],dep[maxn];
ll f[maxn][3][3],tmp[3][3];
int n,S,T,L;
int max(int a,int b){return a>b?a:b;}
int min(int a,int b){return a<b?a:b;}
void dfs(int now,int fa,int* dep)
{
	for(int x:nxt[now])
		if(x!=fa){
			dep[x]=dep[now]+1;
			dfs(x,now,dep);
		}
}
void dp(int now,int fa)
{
	dep[now]=0;
	for(int x:nxt[now])
		if(x!=fa){
			dp(x,now);
			dep[now]=max(dep[now],dep[x]);
		}
	if(dep[now])f[now][0][0]=1;
	else f[now][1][1]=1;
	for(int x:nxt[now])
		if(x!=fa){
			memset(tmp,0,sizeof(tmp));
			int flag=(dep[x]==dep[now]);
			for(int i=0;i<3;i++)
				for(int j=0;j<3;j++)
					for(int k=0;k<3;k++)
						for(int l=0;l<3;l++)
							if(!flag)tmp[i][j]=(tmp[i][j]+3*f[now][i][j]*f[x][k][l])%mod;
							else{
								tmp[i][j]=(tmp[i][j]+f[now][i][j]*f[x][k][l])%mod;
								tmp[min(i+k,2)][j]=(tmp[min(i+k,2)][j]+f[now][i][j]*f[x][k][l])%mod;
								tmp[i][min(j+l,2)]=(tmp[i][min(j+l,2)]+f[now][i][j]*f[x][k][l])%mod;
							}
			memcpy(f[now],tmp,sizeof(tmp));
		}
	++dep[now];
}
int main()
{
	n=read();
	for(int i=1;i<n;i++){
		int x=read(),y=read();
		nxt[x].push_back(y); nxt[y].push_back(x);
	}
	dist1[1]=0;
	dfs(1,-1,dist1);
	S=1;
	for(int i=2;i<=n;i++)
		if(dist1[i]>dist1[S])S=i;
	dist1[S]=0;
	dfs(S,-1,dist1);
	T=1;
	for(int i=2;i<=n;i++)
		if(dist1[i]>dist1[T])T=i;
	dist2[T]=0;
	dfs(T,-1,dist2);
	L=dist1[T];
	if(L&1){
		int C1=0,C2=0;
		for(int u=1;u<=n;u++)
			for(int v:nxt[u])
				if(dist1[u]==L/2&&dist2[v]==L/2){
					C1=u; C2=v;
					break;
				}
		dp(C1,C2); dp(C2,C1);
		ll sum1=(f[C1][1][0]+f[C1][1][1]+f[C1][1][2])%mod,sum2=(f[C2][0][1]+f[C2][1][1]+f[C2][2][1])%mod;
		writeln(sum1*sum2%mod);
	}
	else{
		int C=0;
		for(int i=1;i<=n;i++)
			if(dist1[i]==L/2&&dist2[i]==L/2){
				C=i; break;
			}
		dp(C,-1);
		writeln(f[C][1][1]*inv2%mod);
	}
	// for(int i=1;i<=n;i++){
	// 	for(int j=0;j<3;j++)
	// 		for(int k=0;k<3;k++)
	// 			writesp(f[i][j][k]);
	// 	putchar('\n');
	// }
	return 0;
}