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>
#define F first
#define S second
#define pb push_back
using namespace std;
typedef long long ll;
const int M=998244353;
const int inv2=(M+1)/2;
const int inv3=(M+1)/3;
const int maxn=3e5+3;
vector <int> h[maxn];
int dis[maxn],n,pre[maxn],p,q,d[maxn],m;
ll dp[maxn][4];
void dfs(int u,int fa){
    pre[u]=fa; dis[u]=dis[fa]+1;
    for (auto v:h[u]){
        if (v==fa) continue;
        dfs(v,u);
    }
}
void dfs2(int u,int fa){
    d[u]=d[fa]+1;
    if (d[u]==m){
        dp[u][0]=2; // none
        dp[u][1]=1; // exactly one
        dp[u][2]=3; // all
        dp[u][3]=1; // at least one
        return;
    }
    ll r1=1,r2=0,r3=1,r4=0;
    for (auto v:h[u]){
        if (v==fa) continue;
        dfs2(v,u);
        ll nr1=r1*dp[v][0]%M;
        ll nr2=(r1*dp[v][1]+r2*dp[v][0])%M;
        ll nr3=r3*dp[v][2]%M;
        ll nr4=((r3*dp[v][3]+r4*dp[v][2]-r4*dp[v][3])%M+M)%M;
        r1=nr1; r2=nr2; r3=nr3; r4=nr4;
    }
    dp[u][0]=(r1*3+r4*2)%M;
    dp[u][1]=r2;
    dp[u][2]=r3*3%M;
    dp[u][3]=r4;
    
}
int main(){
    scanf("%d",&n); dis[0]=-1;
    for (int i=1;i<n;i++){
        int u,v; scanf("%d%d",&u,&v);
        h[u].pb(v); h[v].pb(u);
    }
    //puts("B");
    dfs(1,0);
    int s=1;
    for (int i=2;i<=n;i++) if (dis[i]>dis[s]) s=i;
    dfs(s,0);
    int t=s;
    for (int i=1;i<=n;i++) if (dis[i]>dis[t]) t=i;
    m=dis[t]/2; p=t;
    for (int i=0;i<m;i++) p=pre[p];
    if (dis[t]&1){
        q=pre[p];
        d[q]=-1; dfs2(p,q);
        d[p]=-1; dfs2(q,p);
        printf("%lld\n",dp[p][1]*dp[q][1]%M);
    } else {
        ll ans0=1,ans1=0,ans2=0;
        for (auto u:h[p]){
            d[u]=0; dfs2(u,p);
            ll nans0,nans1,nans2,has,none;
            has=dp[u][1]; none=(dp[u][2]+2*(M-dp[u][3]))%M;
            //cout<<has<<' '<<none<<endl;
            //cout<<dp[u][2]<<' '<<dp[u][3]<<endl;
            nans0=ans0*none%M;
            nans1=(ans0*has+ans1*none)%M;
            nans2=(ans1*has+ans2*none)%M;
            ans0=nans0; ans1=nans1; ans2=nans2;
        }
        printf("%lld\n",ans2);
    }
    return 0;
}