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:
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx")
//#undef LOCAL




#include <algorithm>

#include <array>

#include <bitset>

#include <cassert>

#include <complex>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <map>

#include <numeric>

#include <queue>

#include <set>

#include <string>

#include <unordered_map>

#include <unordered_set>

#include <vector>

using namespace std;

using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n - 1); }
template <class T> using V = vector<T>;
template <class T> using VV = V<V<T>>;
inline int read()
{
	int f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}

template <uint MD> struct ModInt {
    using M = ModInt;
    static constexpr uint get_mod() { return MD; }
    const static M G;
    uint v;
    ModInt(ll _v = 0) { set_v(uint(_v % MD + MD)); }
    M& set_v(uint _v) {
        v = (_v < MD) ? _v : _v - MD;
        return *this;
    }
    explicit operator bool() const { return v != 0; }
    M operator-() const { return M() - *this; }
    M operator+(const M& r) const { return M().set_v(v + r.v); }
    M operator-(const M& r) const { return M().set_v(v + MD - r.v); }
    M operator*(const M& r) const { return M().set_v(uint(ull(v) * r.v % MD)); }
    M operator/(const M& r) const { return *this * r.inv(); }
    M& operator+=(const M& r) { return *this = *this + r; }
    M& operator-=(const M& r) { return *this = *this - r; }
    M& operator*=(const M& r) { return *this = *this * r; }
    M& operator/=(const M& r) { return *this = *this / r; }
    bool operator==(const M& r) const { return v == r.v; }
    M pow(ll n) const {
        M x = *this, r = 1;
        while (n) {
            if (n & 1) r *= x;
            x *= x;
            n >>= 1;
        }
        return r;
    }
    M inv() const { return pow(MD - 2); }
    friend ostream& operator<<(ostream& os, const M& r) { return os << r.v; }
};
// using Mint = ModInt<998244353>;
// template<> const Mint Mint::G = Mint(3);

int stack[20];
template<typename T>inline void write(T x)
{
	if(x<0){putchar('-');x=-x;}
    if(!x){putchar('0');return;}
    int top=0;
    while(x)stack[++top]=x%10,x/=10;
    while(top)putchar(stack[top--]+'0');
}
template<typename T>inline void pr1(T x){write(x);putchar(' ');}
template<typename T>inline void pr2(T x){write(x);putchar('\n');}
using Mint = ModInt<998244353>;

VV<int> g;

int mdp, mv;
void dfs(int p, int b, int ndp = 0) {
    if (mdp <= ndp) {
        mdp = ndp;
        mv = p;
    }
    for (int d: g[p]) {
        if (d == b) continue;
        dfs(d, p, ndp + 1);
    }
}

V<int> path;
bool dfs_path(int p, int b, int t) {
    if (p == t) {
        path.push_back(p);
        return true;
    }
    for (int d: g[p]) {
        if (d == b) continue;
        if (dfs_path(d, p, t)) {
            path.push_back(p);
            return true;
        }
    }
    return false;
}

int U;

using P = array<Mint, 3>;

P solve(int p, int b, int ndps = 0) {
    if (g[p].size() == 1) {
        // leaf
        if (ndps == U) {
            // rad
            return {Mint(2), Mint(1), Mint(0)};
        } else {
//            dbg(p, b, P{Mint(3), Mint(0)});
            return {Mint(3), Mint(0), Mint(0)};
        }
    }
    P dp = {Mint(1), Mint(0), Mint(0)};
    for (auto d: g[p]) {
        if (d == b) continue;
        auto ch = solve(d, p, ndps + 1);
        P ndp = {Mint(0), Mint(0), Mint(0)};
        for (int a = 0; a < 3; a++) {
            for (int b = 0; b < 3; b++) {
                ndp[min(2, a + b)] += dp[a] * ch[b];
            }
        }
        dp = ndp;
    }
    dp[0] = dp[0] * Mint(3) + (dp[1] + dp[2]) * Mint(2);
    return dp;
}

int main() {
    int n;
    n=read();
    g = VV<int>(n);
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        a=read();b=read(); a--; b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    dfs(0, -1);
    int u = mv;
    dfs(mv, -1);
    int v = mv;
    dfs_path(u, -1, v);

    int L = int(path.size());
    if (L % 2) {
        U = (L / 2) - 1;
        int mid = path[L / 2];
                       ;
        V<Mint> dp(4);
        dp[0] = Mint(1);
        for (int d: g[mid]) {
            V<Mint> ndp(4);
            auto x = solve(d, mid);
            Mint x0 = x[0] - (x[1] + x[2]), x1 = x[1];
//            ndp[3] = dp[3] * x0 + dp[2] * x1 + dp[1] * x1;
            ndp[2] = dp[2] * x0 + dp[1] * x1;
            ndp[1] = dp[1] * x0 + dp[0] * x1;
            ndp[0] = dp[0] * x0;
            dp = ndp;
        }
               ;
//        pr.writeln((dp[3] / Mint(2)).v);
//		printf("%");
//		pr2((dp[3]/Mint(2)).v);
		pr2(dp[2].v);
    } else {
        int mid0 = path[L / 2 - 1], mid1 = path[L / 2];
        U = (L / 2 - 1);
        auto x = solve(mid0, mid1);
        auto y = solve(mid1, mid0);
    	pr2((x[1] * y[1]).v);
    }
    return 0;
}