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;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
const ll mod = 998244353;
ll dp[200100][3][3];
vector<ll> paths[200100];
ll N;
vector<ll> C;
ll dist[2][200010];
ll depthmax[2];
void dfs(int idx, int now, int from) {
    for(auto to : paths[now]) {
        if(to == from) continue;
        dist[idx][to] = dist[idx][now] + 1;
        dfs(idx, to, now);
    }
}

void merge(int p, int c) {
    vector<vector<ll>> tmp(3, vector<ll>(3, 0));
    for(int pi = 0; pi < 3; pi++) {
        for(int pj = 0; pj < 3; pj++) {
            for(int ci = 0; ci < 3; ci++) {
                for(int cj = 0; cj < 3; cj++) {
                    for(int len = -1; len <= 1; len++) {
                        int newi = 2;
                        if(len != 1) newi = pi;
                        else if(pi + ci <= 1) newi = pi + ci;
                        int newj = 2;
                        if(len != -1) newj = pj;
                        else if(pj + cj <= 1) newj = pj + cj;
                        tmp[newi][newj] += dp[p][pi][pj] * dp[c][ci][cj];
                        tmp[newi][newj] %= mod;
                    }
                }
            }
        }
    }
    for(int i = 0; i < 3; i++) {
        for(int j = 0; j < 3; j++) {
            dp[p][i][j] = tmp[i][j];
        }
    }
}

void f(int idx, int now, int from) {
    bool IsLeaf = true;
    for(auto to : paths[now]) {
        if(to == from) continue;
        IsLeaf = false;
        f(idx, to, now);
    }
    if(IsLeaf) {
        //cerr << "ifleaf: " << idx << " " << now << " " << depthmax[idx] << " " << dist[idx][now] << endl;
        if(dist[idx][now] == depthmax[idx]) {
            dp[now][1][1] = 1;
        } else {
            dp[now][0][0] = 1;
        }
        return;
    }
    dp[now][0][0] = 1;
    for(auto to : paths[now]) {
        if(to == from) continue;
        merge(now, to);
    }
    return;
}

ll beki(ll a, ll b) {
    if(b == 0) return 1;
    ll ret = beki(a, b / 2);
    ret = ret * ret % mod;
    if(b & 1) ret = ret * a % mod;
    return ret;
}

int main() {
    cin >> N;
    for(int i = 0; i < N - 1; i++) {
        ll a, b;
        cin >> a >> b;
        a--;
        b--;
        paths[a].push_back(b);
        paths[b].push_back(a);
    }
    dfs(0, 0, -1);
    ll v1 = 0;
    for(int i = 0; i < N; i++) {
        if(dist[0][v1] < dist[0][i]) v1 = i;
    }
    dfs(1, v1, -1);
    ll v2 = 0;
    for(int i = 0; i < N; i++) {
        if(dist[1][v2] < dist[1][i]) v2 = i;
    }
    dist[0][v2] = 0;
    dfs(0, v2, -1);
    C.push_back(0);
    //cerr << v1 << " " << v2 << endl;
    for(int i = 1; i < N; i++) {
        //cerr << i << " " << dist[0][i] << " " << dist[1][i] << endl;
        if(dist[0][i] + dist[1][i] != dist[0][v1]) continue;
        if(max(dist[0][C[0]], dist[1][C[0]]) == max(dist[0][i], dist[1][i])) {
            C.push_back(i);
        }
        if(max(dist[0][C[0]], dist[1][C[0]]) > max(dist[0][i], dist[1][i])) {
            C.clear();
            C.push_back(i);
        }
    }
    assert(C.size() == 1 or C.size() == 2);
    /*
    cerr << "--------C--------" << endl;
    for(auto tmp : C) {
        cerr << tmp << " ";
    }
    cerr << endl;
    */
    for(int i = 0; i < N; i++) {
        dist[0][i] = dist[1][i] = 0;
    }
    for(int i = 0; i < C.size(); i++) {
        dfs(i, C[i], C[(i+1) % C.size()]);
        for(int j = 0; j < N; j++) {
            chmax(depthmax[i], dist[i][j]);
        }
        //cerr << i << " " << C[i] << " " << depthmax[i] << endl;
        f(i, C[i], C[(i+1)%C.size()]);
        for(int j = 0; j < 3; j++) {
            for(int k = 0; k < 3; k++) {
                //cerr << C[i] << " " << j << " " << k << " " << dp[C[i]][j][k] << endl;
            }
        }
    }
    if(C.size() == 1) {
        cout << dp[C[0]][1][1] * beki(2, mod - 2) % mod << endl;
        return 0;
    } else {
        ll ans = 0;
        for(int i0 = 0; i0 < 3; i0++) {
            for(int j0 = 0; j0 < 3; j0++) {
                for(int i1 = 0; i1 < 3; i1++) {
                    for(int j1 = 0; j1 < 3; j1++) {
                        ll ok = 0;
                        if(i0 == 1 and j1 == 1) ok++;
                        if(j0 == 1 and i1 == 1) ok++;
                        ans += ok * dp[C[0]][i0][j0] * dp[C[1]][i1][j1] % mod;
                        ans %= mod;
                    }
                }
            }
        }
        ans *= beki(2, mod - 2);
        ans %= mod;
        cout << ans << endl;
    }
    return 0;
}