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<cstdio>
#include<algorithm>
#include<vector>
#define N_ 201000
using namespace std;
int n, D1[N_], D2[N_], MD, C[N_], DD[N_];
long long po[N_], D[N_][3], Mod = 998244353;
vector<int>E[N_];
void DFS(int a, int pp, int *d) {
	for (auto &x : E[a]) {
		if (x == pp)continue;
		d[x] = d[a] + 1;
		DFS(x, a, d);
	}
}
void Add_Edge(int a, int b) {
	E[a].push_back(b);
	E[b].push_back(a);
}
void Del_Edge(int a, int b) {
	int sz = E[a].size();
	for (int i = 0; i < sz; i++) {
		if (E[a][i] == b) {
			swap(E[a][i], E[a][sz - 1]);
			E[a].pop_back();
			return;
		}
	}
}
void Go(int a, int pp) {
	vector<int>T;
	for (auto &x : E[a]) {
		if (x == pp)continue;
		Go(x, a);
		T.push_back(x);
	}
	if (T.empty()) {
		if (DD[a] == MD) {
			D[a][0] = 2, D[a][1] = 1;
		}
		else {
			D[a][0] = 3;
		}
		return;
	}
	D[a][0] = 1, D[a][1] = 0, D[a][2] = 0;
	for (auto &x : T) {
		long long d0 = D[a][0] * D[x][0];
		long long d1 = D[a][0] * D[x][1] + D[a][1] * D[x][0];
		long long d2 = D[a][0] * D[x][2] + D[a][1] * (D[x][1] + D[x][2]) + D[a][2] * (D[x][0] + D[x][1] + D[x][2]);
		D[a][0] = d0 % Mod, D[a][1] = d1 % Mod, D[a][2] = d2 % Mod;
	}
	D[a][0] = (D[a][0] * 3 + D[a][1] * 2 + D[a][2] * 2) % Mod;
}
int main() {
	int i, mid;
	scanf("%d", &n);
	for (i = 1; i < n; i++) {
		int a, b;
		scanf("%d%d", &a, &b);
		E[a].push_back(b);
		E[b].push_back(a);
	}
	D1[1] = 0;
	DFS(1, 0, D1);
	int Mx = -1, a = -1, b = -1;
	for (i = 1; i <= n; i++) {
		if (Mx < D1[i])Mx = D1[i], a = i;
	}
	D1[a] = 0;
	DFS(a, 0, D1);
	Mx = -1;
	for (i = 1; i <= n; i++) {
		if (Mx < D1[i])Mx = D1[i], b = i;
	}
	D2[b] = 0;
	DFS(b, 0, D2);
	if (Mx % 2 == 1) {
		int t1, t2;
		for (i = 1; i <= n; i++) {
			if (D1[i] + D2[i] == Mx) {
				if (D1[i] == Mx / 2) {
					t1 = i;
				}
				if (D2[i] == Mx / 2) {
					t2 = i;
				}
			}
		}
		Del_Edge(t1, t2); Del_Edge(t2, t1);
		n++;
		Add_Edge(t1, n); Add_Edge(t2, n);
		D1[a] = 0, D2[b] = 0;
		DFS(a, 0, D1);
		DFS(b, 0, D2);
		Mx = D1[b];
	}
	MD = 1e9;
	for (i = 1; i <= n; i++) {
		if (max(D1[i], D2[i]) < MD) {
			MD = max(D1[i], D2[i]);
			mid = i;
		}
	}
	DFS(mid, 0, DD);
	po[0] = 1;
	for (i = 1; i <= n; i++)po[i] = po[i - 1] * 3 % Mod;
	long long dd[3] = { 1,0,0 };
	for (auto &x : E[mid]) {
		Go(x, mid);
		long long g = (D[x][0] - D[x][1] - D[x][2] + Mod + Mod) % Mod;
		long long dd0 = dd[0] * g;
		long long dd1 = dd[0] * D[x][1] + dd[1]* g;
		long long dd2 = dd[1] * D[x][1] + dd[2] * g;
		dd[0] = dd0%Mod, dd[1] = dd1 % Mod, dd[2] = dd2 % Mod;
	}
	printf("%lld\n", dd[2]);

}