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

struct llm{
    ll value=0;
    llm(const ll& val=0){this->value = (MOD + val % MOD) % MOD;}
    llm(const int& val){this->value = (MOD + val % MOD) % MOD;}
    llm(const llm& a) { llm(a.value); }
    llm inv(){ll a = 1;ll b = this->value;for(ll m=MOD-2;m>0;m/=2){if(m&1){a=a*b%MOD;}b=b*b%MOD;}return llm(a);}
    llm &operator+=(const llm &a) {this->value = (this->value + a.value) % MOD;return *this;}
    llm &operator-=(const llm &a) {this->value = (this->value - a.value + MOD) % MOD;return *this;}
    llm &operator*=(const llm &a) {this->value = (this->value * a.value) % MOD; return *this; }
    explicit operator ll() const{return (ll)value;}
    explicit operator int() const{return (int)value;}
};
llm operator+(const llm &a, const llm &b) { return llm(a.value + b.value); }
llm operator-(const llm &a, const llm &b) { return llm(a.value - b.value); }
llm operator*(const llm &a, const llm &b) { return llm(a.value * b.value); }
#define pllm pair<llm,llm>

ll N, Len;
vector<ll> abv[202020];
vector<ll> abl[202020];
llm dp[202020][4];
ll i, j, k;
llm 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;
    llm c = 1;
    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 *= dp[b][0];
        dp[a][2] *= dp[b][2];
    }
    dp[a][0] = dp[a][2] * 2 + c;
    fornum(i,0,abv[a].size()){
        ll b = abv[a][i];
        if(b==p){
            continue;
        }
        dp[a][1] += c * dp[b][1] * dp[b][0].inv();
    }
    dp[a][2] *= 3;
}

ll lencalc(ll a,ll p,ll 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];
            }
        }
        dfs(a.first, a.second, Len / 2);
        dfs(a.second, a.first, Len / 2);
        ans = dp[a.first][1] * dp[a.second][1];
    }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;
        dfs(a, 0, Len / 2);

        llm c = 1;
        fornum(i,0,abv[a].size()){
            ll b = abv[a][i];
            c *= dp[b][0] * 2 - dp[b][2];
        }
        llm d = 0;
        fornum(i,0,abv[a].size()){
            ll b = abv[a][i];
            ans += d * dp[b][1] * (dp[b][0] * 2 - dp[b][2]).inv();
            d += c * dp[b][1] * (dp[b][0] * 2 - dp[b][2]).inv();
        }
    }
    
    printf("%lld", (ll)ans);

    return 0;
}