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;

using ll = long long;

template<int MOD>
struct ModInt {
   using Mint = ModInt;
   int val;
   ModInt(ll __val = 0) { fix(__val % MOD + MOD); }
   Mint& fix(int __val) { val = __val; if (val >= MOD) val -= MOD; return *this; }
   explicit operator int() { return val; }
   Mint operator + (const Mint &mt) const { return Mint().fix(val + mt.val); }
   Mint operator - (const Mint &mt) const { return Mint().fix(val - mt.val + MOD); }
   Mint operator * (const Mint &mt) const { return Mint().fix(ll(val) * mt.val % MOD + MOD); }
   Mint& operator += (const Mint &mt) { return *this = *this + mt; }
   Mint& operator -= (const Mint &mt) { return *this = *this - mt; }
   Mint& operator *= (const Mint &mt) { return *this = *this * mt; }
   Mint pow(int y) const {
      Mint x = *this;
      Mint ans(1);
      for (; y > 0; y >>= 1, x *= x) {
         if (y & 1) ans *= x;
      }
      return ans;
   }
   Mint operator -() const { return Mint().fix(MOD - val); }
   Mint inv() const { return pow(MOD - 2); }
   Mint operator / (const Mint &mt) const { return *this * mt.inv(); }
   Mint& operator /= (const Mint &mt) const { return *this / mt; }
   friend ostream& operator<<(ostream& os, const Mint& mt) { return os << mt.val; }
};

using Mint = ModInt<998244353>;

using State = array<array<Mint, 3>, 3>;

int main() {
   ios_base::sync_with_stdio(false); cin.tie(nullptr);
   int N;
   cin >> N;
   vector<vector<int>> adj(N);
   for (int i = 0; i < N - 1; ++i) {
      int v, u;
      cin >> v >> u;
      adj[--v].emplace_back(--u);
      adj[u].emplace_back(v);
   }
   vector<int> diam;
   {
      vector<int> par(N, -1);
      pair<int, int> best = {0, -1};
      function<void(int, int, int)> dfs = [&](int v, int p, int dist) {
         par[v] = p;
         best = max(best, make_pair(dist, v));
         for (auto u : adj[v]) if (u != p) {
            dfs(u, v, dist + 1);
         }
      };
      dfs(0, -1, 0);
      int v = best.second;
      best = {0, -1};
      dfs(v, -1, 0);
      int u = best.second;
      while (u != v) {
         diam.emplace_back(u);
         u = par[u];
      }
      diam.emplace_back(v);
   }
   int limit = 0;
   function<State(int, int, int)> dfs = [&](int v, int p, int dist) {
      if (adj[v].size() == 1) {
         State cur{};
         if (dist == limit) cur[1][1] = 1;
         else cur[0][0] = 1;
         return cur;
      }
      State cur{};
      cur[0][0] = 1;
      for (int u : adj[v]) if (u != p) {
         auto nxt = dfs(u, v, dist + 1);
         State ncur{};
         for (int cp = 0; cp < 3; ++cp) {
            for (int cn = 0; cn < 3; ++cn) {
               for (int np = 0; np < 3; ++np) {
                  for (int nn = 0; nn < 3; ++nn) {
                     ncur[min(cp + np, 2)][cn] += cur[cp][cn] * nxt[np][nn];
                     ncur[cp][cn] += cur[cp][cn] * nxt[np][nn];
                     ncur[cp][min(cn + nn, 2)] += cur[cp][cn] * nxt[np][nn];
                  }
               }
            }
         }
         cur = ncur;
      }
      return cur;
   };
   if (diam.size() & 1) {
      limit = diam.size() / 2;
      int v = diam[diam.size() / 2];
      auto cur = dfs(v, -1, 0);
      cout << cur[1][1] / 2 << "\n";
   } else {
      limit = (diam.size() / 2) - 1;
      int v0 = diam[(diam.size() / 2) - 1];
      int v1 = diam[diam.size() / 2];
      auto cur0 = dfs(v0, v1, 0);
      auto cur1 = dfs(v1, v0, 0);
      cout << (cur0[1][0] + cur0[1][1] + cur0[1][2]) * (cur1[0][1] + cur1[1][1] + cur1[1][2]) << "\n";
   }
}