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=2e5+5,mod=998244353;
int n,m,dis[N],fa[N],a[N],si[N],rt1,rt2,head[N],nex[N<<1],to[N<<1],tot;
void add(int u,int v){to[++tot]=v;nex[tot]=head[u];head[u]=tot;}
void dfs(int u,int p)
{
    dis[u]=dis[p]+1;
    if(dis[u]>dis[rt1]) rt1=u;
    fa[u]=p;
    for(int i=head[u];i;i=nex[i])
    {
        int v=to[i];if(v==p)continue;
        dfs(v,u);
    }
}
ll dp[N][3][3],p[3][3];
void dfs(int u,int fa,int d)
{
    d==m/2?dp[u][1][1]=1:dp[u][0][0]=1;
    for(int i=head[u];i;i=nex[i])
    {
        int v=to[i];if(v==fa)continue;
        dfs(v,u,d+1);
        memset(p,0,sizeof(p));
        for(int i=0;i<3;i++)
            for(int j=0;j<3;j++)
            for(int k=0;k<3;k++)
                for(int h=0;h<3;h++)
        {
            p[i][j]=(p[i][j]+dp[u][i][j]*dp[v][k][h])%mod;
            p[min(i+k,2)][j]=(p[min(i+k,2)][j]+dp[u][i][j]*dp[v][k][h])%mod;
            p[i][min(j+h,2)]=(p[i][min(j+h,2)]+dp[u][i][j]*dp[v][k][h])%mod;
        }
        for(int i=0;i<3;i++)
            for(int j=0;j<3;j++)
            dp[u][i][j]=p[i][j];
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<n;i++)
    {
        int u,v;scanf("%d%d",&u,&v);add(u,v);add(v,u);
    }
    dfs(1,0);
    rt2=rt1;
    dfs(rt1,0);
    while(fa[rt1]) a[++m]=rt1,rt1=fa[rt1];
    a[++m]=rt1;
    rt1=rt2=0;
    if(m%2==0) rt1=a[m/2],rt2=a[m/2+1];
    else rt1=a[m/2+1];
    m--;
    if(rt1&&rt2)
    {
        dfs(rt1,rt2,0);dfs(rt2,rt1,0);
        printf("%lld\n",(dp[rt1][1][0]+dp[rt1][1][1]+dp[rt1][1][2])*(dp[rt2][1][0]+dp[rt2][1][1]+dp[rt2][1][2])%mod);
    }
    else
    {
        dfs(rt1,0,0);
        printf("%lld\n",dp[rt1][1][1]*(mod-mod/2)%mod);
    }
}