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<cctype>
#include<cstdio>
#include<vector>
#include<cstring>
const int N=300007,P=998244353,i2=P-P/2;
int m,root,len,fa[N],dia[N],f[N][3][3],g[3][3];std::vector<int>e[N];
void inc(int&a,int b){a+=b-P,a+=a>>31&P;}
int mul(int a,int b){return 1ll*a*b%P;}
int read(){int x=0,c=getchar();while(isspace(c))c=getchar();while(isdigit(c))(x*=10)+=c&15,c=getchar();return x;}
void dfs(int u,int dep)
{
    if(dep>len) len=dep,root=u;
    for(int v:e[u]) if(v^fa[u]) fa[v]=u,dfs(v,dep+1);
}
void dp(int u,int fa,int d)
{
    (d==m/2? f[u][1][1]:f[u][0][0])=1;
    for(int v:e[u])
    {
	if(v==fa) continue;
	dp(v,u,d+1),memset(g,0,36);
	for(int x=0;x<3;++x) for(int y=0;y<3;++y) for(int p=0;p<3;++p) for(int q=0;q<3;++q) for(int k=0,r,t;k<3;++k) r=std::min(2,x+p*(k==1)),t=std::min(2,y+q*(k==2)),inc(g[r][t],mul(f[u][x][y],f[v][p][q]));
	memcpy(f[u],g,36);
    }
}
int main()
{
    int n=read(),p,q;
    for(int i=1,u,v;i<n;++i) u=read(),v=read(),e[u].push_back(v),e[v].push_back(u);
    dfs(1,1),memset(fa+1,0,n<<2),len=0,dfs(root,1);
    for(int i=root;i;i=fa[i]) dia[++m]=i;
    if(m&1) p=dia[m/2+1],dp(p,0,0),printf("%d",mul(i2,f[p][1][1]));
    else p=dia[m/2],q=dia[m/2+1],dp(p,q,1),dp(q,p,1),printf("%d",mul((1ll*f[p][1][0]+f[p][1][1]+f[p][1][2])%P,(1ll*f[q][1][0]+f[q][1][1]+f[q][1][2])%P));
}