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 rep(i, a, b) for (int i = (a); i <= int(b); i++)
#define per(i, a, b) for (int i = (a); i >= int(b); i--)
#define fi first
#define se second
using namespace std;

typedef long long ll;
const int maxn = 2e5, mod = 998244353;
int n, f[maxn + 3], mx[maxn + 3], se[maxn + 3], g[maxn + 3];
int far[maxn + 3], h[maxn + 3][3][3], t[3][3];
vector<int> G[maxn + 3];

void dfs(int u, int p = 0) {
	rep(i, 0, G[u].size() - 1) {
		int v = G[u][i];
		if (v == p) continue;
		dfs(v, u);
		f[u] = max(f[u], f[v] + 1);
		if (!mx[u] || f[v] >= f[mx[u]]) {
			se[u] = mx[u], mx[u] = v;
		} else if (!se[u] || f[v] >= f[se[u]]) {
			se[u] = v;
		}
	}
}

void down(int u, int p = 0) {
	rep(i, 0, G[u].size() - 1) {
		int v = G[u][i];
		if (v == p) continue;
		if (v == mx[u]) {
			g[v] = max(g[u], f[se[u]] + 1) + 1;
		} else {
			g[v] = max(g[u], f[mx[u]] + 1) + 1;
		}
		down(v, u);
	}
	g[u] = max(f[u], g[u]);
}

void work(int u, int p = 0) {
	rep(i, 0, G[u].size() - 1) {
		int v = G[u][i];
		if (v == p) continue;
		work(v, u);
		far[u] = max(far[u], far[v] + 1);
	}
	if (!far[u]) { h[u][1][1] = 1; return; }
	h[u][0][0] = 1;
	rep(i, 0, G[u].size() - 1) {
		int v = G[u][i];
		if (v == p) continue;
		memset(t, 0, sizeof(t));
		rep(a, 0, 2) rep(b, 0, 2) if (h[u][a][b]) {
			rep(c, 0, 2) rep(d, 0, 2) if (h[v][c][d]) {
				int x = 1ll * h[u][a][b] * h[v][c][d] % mod;
				rep(e, -1, 1) {
					int t1 = min(2, (far[v] + e == far[u]) ? a + c : a);
					int t2 = min(2, (far[v] - e == far[u]) ? b + d : b);
					t[t1][t2] += x, t[t1][t2] >= mod ? t[t1][t2] -= mod : 0;
				}
			}
		}
		memcpy(h[u], t, sizeof(h[u]));
	}
}

int main() {
	scanf("%d", &n);
	rep(i, 1, n - 1) {
		int u, v; scanf("%d %d", &u, &v);
		G[u].push_back(v), G[v].push_back(u);
	}
	f[0] = -1;
	dfs(1);
	down(1);
	int mn = n;
	rep(i, 1, n) mn = min(mn, g[i]);
	int a = 0, b = 0, c = 0;
	rep(i, 1, n) if (g[i] == mn) {
		if (++c == 1) a = i;
		else if (c == 2) b = i;
		else exit(1);
	}
	if (c == 1) {
		work(a);
		printf("%d\n", int(1ll * (mod + 1) / 2 * h[a][1][1] % mod));
	} else {
		work(a, b), work(b, a);
		printf("%d\n", int(((ll)h[a][1][0] + h[a][1][1] + h[a][1][2]) * ((ll)h[b][1][0] + h[b][1][1] + h[b][1][2]) % mod));
	}
	return 0;
}