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;

const int N = 2e5 + 5, mod = 998244353;

vector<int> g[N];
int par[N], lv[N];
long long dp[N][3], tmp[3];

void add(long long & var, long long val) {
  var += val;
  if (var >= mod)
    var -= mod;
}

void dfs(int v, int p) {
  par[v] = p;
  for (int u : g[v]) {
    if (u == p) continue;
    lv[u] = lv[v] + 1;
    dfs(u, v);
  }
}

void solve(int v, int p, int depth) {
  memset(dp[v], 0, sizeof dp[v]);
  dp[v][(depth == 0)] = 1;
  --depth;
  for (int u : g[v]) {
    if (u == p) continue;
    solve(u, v, depth);
    memset(tmp, 0, sizeof tmp);
    for (int i = 0; i < 3; ++i) {
      for (int j = 0; j < 3; ++j) {
        add(tmp[min(i+j, 2)], dp[v][i] * dp[u][j] % mod);
        add(tmp[i], 2LL * dp[v][i] * dp[u][j] % mod);
      }
    }
    for (int i = 0; i < 3; ++i)
      dp[v][i] = tmp[i];
  }
}

int main() {
  int n;
  scanf("%d", &n);
  for (int i = 1; i < n; ++i) {
    int u, v;
    scanf("%d %d", &u, &v);
    --u, --v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  lv[0] = 0;
  dfs(0, 0);
  int root = 0;
  for (int i = 0; i < n; ++i) {
    if (lv[i] > lv[root])
      root = i;
  }
  lv[root] = 0;
  dfs(root, -1);
  int leaf = 0;
  for (int i = 0; i < n; ++i) {
    if (lv[i] > lv[leaf])
      leaf = i;
  }
  int diam = lv[leaf];
  long long ans = 0;
  if (diam & 1) {
    int a = leaf;
    for (int i = 0; i < diam/2; ++i) {
      a = par[a];
    }
    int b = par[a];
    solve(a, b, diam/2);
    solve(b, a, diam/2);
    ans = 1LL * dp[a][1] * dp[b][1] % mod;
  }
  else {
    int c = leaf;
    for (int i = 0; i < diam/2; ++i) {
      c = par[c];
    }
    long long best[3];
    memset(best, 0, sizeof best);
    best[0] = 1;
    for (int u : g[c]) {
      solve(u, c, diam/2-1);
      memset(tmp, 0, sizeof tmp);
      if (diam == 2)
        dp[u][0] = dp[u][1];
      else {
        dp[u][0] = (dp[u][0] - dp[u][1] - dp[u][2]) % mod;
        dp[u][0] = (3LL * dp[u][0] + 4LL * dp[u][1] + 4LL * dp[u][2]) % mod;
      }
      tmp[0] = (best[0] * dp[u][0]) % mod;
      tmp[1] = (best[0] * dp[u][1] + best[1] * dp[u][0]) % mod;
      tmp[2] = (best[1] * dp[u][1] + best[2] * dp[u][0]) % mod;
      for (int i = 0; i < 3; ++i)
        best[i] = tmp[i];
    }
    ans = best[2];
  }
  ans %= mod;
  if (ans < 0)
    ans += mod;
  printf("%lld\n", ans);
  return 0;
}