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;
#define ll long long
#define REP(i,a,b) for(int i=(a),_end_=(b);i<=_end_;i++)
#define DREP(i,a,b) for(int i=(a),_end_=(b);i>=_end_;i--)
#define EREP(i,u) for(int i=start[u];i;i=e[i].next)
#define fi first
#define se second
#define mkr(a,b) make_pair(a,b)
#define SZ(A) ((int)A.size())
template<class T>inline void chkmax(T &a,T b){ if(a<b)a=b;}
template<class T>inline void chkmin(T &a,T b){ if(a>b)a=b;}
inline int read()
{
    int s=0,f=1; char ch=getchar();
    while(!isdigit(ch) && ch!='-')ch=getchar();
    if(ch=='-')ch=getchar(),f=-1;
    while(isdigit(ch))s=s*10+ch-'0',ch=getchar();
    return ~f?s:-s;
}

const int maxn=1e6+20;
const ll mod=998244353;

vector<int>ed[maxn];
int n;

inline void init()
{
    n=read();
    REP(i,1,n-1)
    {
	int u=read(),v=read();
	ed[u].push_back(v);
	ed[v].push_back(u);
    }
}

int cir[maxn],len;

inline int bfs(int S)
{
    static int dis[maxn],pre[maxn];
    memset(dis,-1,sizeof(dis));
    queue<int>q;
    q.push(S); dis[S]=0; pre[S]=0;
    while(!q.empty())
    {
	int u=q.front(); q.pop();
	for(int v:ed[u])
	    if(dis[v]==-1)
		q.push(v),dis[v]=dis[u]+1,pre[v]=u;
    }
    int T=0,tmx=0;
    REP(i,1,n)if(dis[i]>tmx)tmx=dis[i],T=i;
    int x=T;
    len=0;
    while(x)cir[++len]=x,x=pre[x];
    reverse(cir+1,cir+len+1);
    return T;
}

int rt;

inline void find_Len()
{
    int S=bfs(1);
    int T=bfs(S);
    if(len%2==1)rt=cir[len+1>>1];
    else {
	int x=cir[len>>1],y=cir[len+2>>1];
	ed[x].erase(find(ed[x].begin(),ed[x].end(),y));
	ed[y].erase(find(ed[y].begin(),ed[y].end(),x));
	++n;
	ed[x].push_back(n); ed[y].push_back(n);
	ed[n]={x,y};
	rt=n;
    }
}

int ans;

int deep[maxn];
ll dp[maxn][3][3];

void dfs(int u,int fa)
{
    int son=0;
    for(int v:ed[u])
    {
	if(v==fa)continue;
	deep[v]=deep[u]+1;
	dfs(v,u);
	son++;
    }
    if(!son)dp[u][deep[u]==len/2][deep[u]==len/2]=1;
    else {
	dp[u][0][0]=1;
	for(int v:ed[u])
	{
	    if(v==fa)continue;
	    ll g[3][3]={0};
	    REP(a,0,2)REP(b,0,2)REP(c,0,2)REP(d,0,2)REP(edge,-1,1)
		(g[min(a+c*(edge==1),2)][min(b+d*(edge==-1),2)]+=dp[u][a][b]*dp[v][c][d])%=mod;
	    REP(a,0,2)REP(b,0,2)dp[u][a][b]=g[a][b];
	}
    }
}

inline void doing()
{
    find_Len();
    dfs(rt,0);
    printf("%lld\n",(ll)dp[rt][1][1]*(mod+1>>1)%mod);
}

int main()
{
    init();
    doing();
    return 0;
}