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 ll long long
#define fornum(A,B,C) for(A=B;A<C;++A)
#define pii pair<int,int>
#define pll pair<ll,ll>

using namespace std;

/////////////////////////////////////////////////////
#define MOD 998244353ll
ll moddiv(ll a,ll b){
    a %= MOD;
    b %= MOD;
    for(ll m=MOD-2;m>0;m/=2){
        if(m&1){
            a=a*b%MOD;
        }
        b=b*b%MOD;
    }
    return a;
}


ll N,Len;
vector<ll> abv[202020];
vector<ll> abl[202020];
ll mk[202020],p3[202020];
ll dp[202020][4];
ll i, j, k;
ll ans;

void dfs(ll a,ll p,ll d)
{
    if(abv[a].size()==1){
        dp[a][2] = 3;
        if(d==0){
            dp[a][0] = 2;
            dp[a][1] = 1;
        }else{
            dp[a][0] = 3;
        }
        return;
    }
    ll i;
    ll c = 1, e = 0;
    dp[a][2] = 1;
    fornum(i,0,abv[a].size()){
        ll b = abv[a][i];
        if(b==p){
            continue;
        }
        dfs(b, a, d - 1);
        c = c * dp[b][0] % MOD;
        dp[a][2] *= dp[b][2];
        dp[a][2] %= MOD;
    }
    dp[a][0] = (dp[a][2] * 2 + c) % MOD;
    fornum(i,0,abv[a].size()){
        ll b = abv[a][i];
        if(b==p){
            continue;
        }
        dp[a][1] += moddiv(c * dp[b][1], dp[b][0]);
        dp[a][1] %= MOD;
    }
    dp[a][2] *= 3;
    dp[a][2] %= MOD;
}

ll lencalc(ll a,ll p,ll d){
    //printf("%lld,%lld,%lld\n", p, a, d);
    ll i = 0,  ret = 0;
    pll c = {0, 0};
    fornum(i,0,abv[a].size()){
        ll b = abv[a][i];
        if(b==p)
            continue;
        if(c.first<=abl[a][i]){
            c.second = c.first;
            c.first = abl[a][i];
        }else if(c.second<=abl[a][i]){
            c.second = abl[a][i];
        }
    }
    fornum(i,0,abv[a].size()){
        ll b = abv[a][i];
        if(b==p){
            abl[a][i] = d;
            continue;
        }
        ll r = 0;
        if(c.first==abl[a][i]){
            r = lencalc(b, a, max(d, c.second) + 1);
        }else{
            r = lencalc(b, a, max(d, c.first) + 1);
        }
        abl[a][i] = r;
        ret = max(ret, r);
    }
    return ret + 1;
}


int main(){
    scanf("%lld", &N);
    fornum(i,1,N){
        ll a, b;
        scanf("%lld%lld", &a, &b);
        abv[a].push_back(b);
        abl[a].push_back(0);
        abv[b].push_back(a);
        abl[b].push_back(0);
    }
    lencalc(1, 0, 0);
    lencalc(1, 0, 0);
    fornum(i,1,N+1){
        if(abv[i].size()==1){
            Len = max(Len, abl[i][0]);
        }
    }

    if(Len%2){
        pll a = {0, 0};
        fornum(i,1,N+1){
            fornum(j,0,abv[i].size()){
                if((Len+1)/2==abl[i][j]){
                    break;
                }
            }
            if(j<abv[i].size()){
                a.first = i;
                a.second = abv[i][j];
            }
        }
        //printf("b%lld,%lld\n", a.first, a.second);
        dfs(a.first, a.second, Len / 2);
        dfs(a.second, a.first, Len / 2);
        ans = dp[a.first][1] * dp[a.second][1] % MOD;
    }else{
        fornum(i,1,N+1){
            if(abv[i].size()==1)
                continue;
            sort(abl[i].begin(), abl[i].end(),greater<ll>());
            if(abl[i][0]==abl[i][1])
                break;
        }
        ll a = i;
        //printf("a%lld\n", a);
        dfs(a, 0, Len / 2);
        ll c = 1;
        fornum(i,0,abv[a].size()){
            ll b = abv[a][i];
            //printf("cc%lld,%lld,%lld\n", b, dp[b][0], dp[b][1]);
            c = c * (dp[b][0] * 2 - dp[b][2] + MOD) % MOD;
        }
        ll d = 0;
        fornum(i,0,abv[a].size()){
            ll b = abv[a][i];
            ans += moddiv(d * dp[b][1], dp[b][0] * 2 - dp[b][2] + MOD);
            ans %= MOD;
            d += moddiv(c * dp[b][1], dp[b][0] * 2 - dp[b][2] + MOD);
            d %= MOD;
        }
    }
    
    printf("%lld", ans);

    return 0;
}