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;

const int N=200000,mod=998244353,inv2=499122177;

int add(int a,int b,int p=mod){return a+b>=p?a+b-p:a+b;}
int sub(int a,int b,int p=mod){return a-b<0?a-b+p:a-b;}
int mul(int a,int b,int p=mod){return (LL)a*b%p;}
void sadd(int &a,int b,int p=mod){a=add(a,b,p);}
void ssub(int &a,int b,int p=mod){a=sub(a,b,p);}
void smul(int &a,int b,int p=mod){a=mul(a,b,p);}

int n;
struct side{
  int y,next;
}e[N*2+9];
int lin[N+9],cs;

void Ins(int x,int y){e[++cs].y=y;e[cs].next=lin[x];lin[x]=cs;}
void Ins2(int x,int y){Ins(x,y);Ins(y,x);}

void into(){
  scanf("%d",&n);
  for (int i=1;i<n;++i){
	int x,y;
	scanf("%d%d",&x,&y);
	Ins2(x,y);
  }
}

int dis[N+9],pre[N+9];
queue<int>q;

int Bfs_dis(int st){
  int res=st;
  for (int i=1;i<=n;++i) dis[i]=0;
  dis[st]=1;pre[st]=0;q.push(st);
  for (;!q.empty();){
	int t=q.front();q.pop();
	if (dis[t]>dis[res]) res=t;
	for (int i=lin[t];i;i=e[i].next)
	  if (!dis[e[i].y]){
		dis[e[i].y]=dis[t]+1;
		pre[e[i].y]=t;
		q.push(e[i].y);
	  }
  }
  return res;
}

int dia,d[N+9],cd;

void Get_dia(){
  int k=Bfs_dis(Bfs_dis(1));
  dia=dis[k]-1;
  for (;k;k=pre[k]) d[++cd]=k;
}

int dp[N+9][3][3],tmp[3][3];

void Dfs_dp(int k,int fa,int dep){
  dep==dia>>1?dp[k][1][1]=1:dp[k][0][0]=1;
  for (int i=lin[k];i;i=e[i].next){
	int y=e[i].y;
	if (y==fa) continue;
	Dfs_dp(e[i].y,k,dep+1);
	for (int i=0;i<3;++i)
	  for (int j=0;j<3;++j)
		for (int u=0;u<3;++u)
		  for (int v=0;v<3;++v)
			for (int t=0;t<3;++t){
			  int p=min(2,i+u*(t==1)),q=min(2,j+v*(t==2));
			  sadd(tmp[p][q],mul(dp[k][i][j],dp[y][u][v]));
			}
	for (int i=0;i<3;++i)
	  for (int j=0;j<3;++j) dp[k][i][j]=tmp[i][j],tmp[i][j]=0;
  }
}

int ans;

void Get_dp(){
  if (cd&1){
	int k=d[cd+1>>1];
	Dfs_dp(k,0,0);
	ans=mul(dp[k][1][1],inv2);
  }else{
	int x=d[cd>>1],y=d[cd+2>>1];
	Dfs_dp(x,y,0);Dfs_dp(y,x,0);
	ans=mul(add(dp[x][1][0],add(dp[x][1][1],dp[x][1][2])),add(dp[y][0][1],add(dp[y][1][1],dp[y][2][1])));
  }
}

void work(){
  Get_dia();
  Get_dp();
}

void outo(){
  printf("%d\n",ans);
}

int main(){
  into();
  work();
  outo();
  return 0;
}