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 maxn=200005;
const int mod=998244353;
int n,diam,s,t,ans;
vector<int>edge[maxn];
int dep[maxn],par[maxn],dp[maxn][3][3],ndp[3][3];
bool leaf[maxn];
void Add(int &a,int b){
	a+=b;
	if(a>=mod)a-=mod;
}

void predfs(int x,int p,int d){
	par[x]=p;
	dep[x]=d;
	for(int i=0;i<int(edge[x].size());i++)
		if(edge[x][i]!=p)predfs(edge[x][i],x,d+1);
}
void dfs(int x,int p,int d){
	if(d==diam/2)leaf[x]=true;
	dp[x][0][0]=1;
	for(int i=0;i<int(edge[x].size());i++){
		int y=edge[x][i];
		if(y==p)continue;
		dfs(y,x,d+1);
		for(int a=0;a<3;a++)for(int b=0;b<3;b++)ndp[a][b]=0;
		for(int a=0;a<3;a++)for(int b=0;b<3;b++)if(dp[x][a][b])
			for(int c=0;c<3;c++)for(int d=0;d<3;d++)if(dp[y][c][d]){
				int cur=1LL*dp[x][a][b]*dp[y][c][d]%mod;
				if(leaf[y]){
					Add(ndp[min(2,a+1)][b],cur);
					Add(ndp[a][b],cur);
					Add(ndp[a][min(2,b+1)],cur);
				}
				else{
					Add(ndp[min(2,a+c)][b],cur);
					Add(ndp[a][b],cur);
					Add(ndp[a][min(2,b+d)],cur);
				}
			}
		for(int a=0;a<3;a++)for(int b=0;b<3;b++)dp[x][a][b]=ndp[a][b];
	}
}

int main(){
	scanf("%d",&n);
	for(int i=1;i<=n-1;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		edge[u].push_back(v);
		edge[v].push_back(u);
	}
	predfs(1,0,0);
	for(int i=1;i<=n;i++)if(!s||dep[i]>dep[s])s=i;
	predfs(s,0,0);
	for(int i=1;i<=n;i++)if(!t||dep[i]>dep[t])t=i;
	diam=dep[t];
	int u=t;
	for(int i=1;i<=diam/2;i++)u=par[u];
	if(diam%2==0){
		dfs(u,0,0);
		ans=dp[u][1][1];
	}
	else{
		int v=par[u];
		dfs(u,v,0);
		dfs(v,u,0);
		int ansu=(1LL*dp[u][0][1]+dp[u][1][1]+dp[u][2][1])%mod;
		int ansv=(1LL*dp[v][1][0]+dp[v][1][1]+dp[v][1][2])%mod;
		ans=2LL*ansu%mod*ansv%mod;
	}
	printf("%d\n",1LL*ans*(mod+1)/2%mod);
	return 0;
}