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:
/*
For even diameter D, label tree vertices with -D/2..D/2 so adjacent vertices have label diff <= 1,
and there are exactly one vertex labelled D/2 and one -D/2.
*/
#include <bits/stdc++.h>
using namespace std;
//#define cerr if (false) cerr
#define db(x) cerr << #x << "=" << x << endl
#define db2(x, y) cerr << #x << "=" << x << "," << #y << "=" << y << endl
#define db3(x, y, z) cerr << #x << "=" << x << "," << #y << "=" << y << "," << #z << "=" << z << endl
#define dbv(v) cerr << #v << "="; for (auto _x : v) cerr << _x << ", "; cerr << endl
#define dba(a, n) cerr << #a << "="; for (int _i = 0; _i < (n); ++_i) cerr << a[_i] << ", "; cerr << endl
template <typename A, typename B>
ostream& operator<<(ostream& os, const pair<A, B>& x) {
	return os << "(" << x.first << "," << x.second << ")";
}
typedef long long ll;
typedef long double ld;
const int MOD = 998244353;
struct Mint {
	int val;
	Mint() { val = 0; }
	Mint(const ll& x) {
		val = (-MOD <= x && x < MOD) ? x : x % MOD;
		if (val < 0) val += MOD;
	}
	template <typename U>
	explicit operator U() const { return (U)val; }
	friend bool operator==(const Mint& a, const Mint& b) { return a.val == b.val; }
	friend bool operator!=(const Mint& a, const Mint& b) { return !(a == b); }
	friend bool operator<(const Mint& a, const Mint& b) { return a.val < b.val; }
	Mint& operator+=(const Mint& m) { if ((val += m.val) >= MOD) val -= MOD; return *this; }
	Mint& operator-=(const Mint& m) { if ((val -= m.val) < 0) val += MOD; return *this; }
	Mint& operator*=(const Mint& m) { val = (ll)val * m.val % MOD; return *this; }
	friend Mint modex(Mint a, ll p) {
		assert(p >= 0);
		Mint ans = 1;
		for (; p; p >>= 1, a *= a) if (p & 1) ans *= a;
		return ans;
	}
	Mint& operator/=(const Mint& m) { return *this *= modex(m, MOD - 2); }
	Mint& operator++() { return *this += 1; }
	Mint& operator--() { return *this -= 1; }
	Mint operator++(int) { Mint result(*this); *this += 1; return result; }
	Mint operator--(int) { Mint result(*this); *this -= 1; return result; }
	Mint operator-() const { return Mint(-val); }
	friend Mint operator+(Mint a, const Mint& b) { return a += b; }
	friend Mint operator-(Mint a, const Mint& b) { return a -= b; }
	friend Mint operator*(Mint a, const Mint& b) { return a *= b; }
	friend Mint operator/(Mint a, const Mint& b) { return a /= b; }
	friend ostream& operator<<(ostream& os, const Mint& x) { return os << x.val; }
};
const int MAXN = 200005;
vector<int> E[MAXN];
Mint F[MAXN][3][3];
int lim;
void go(int x, int p = -1, int h = 0) {
	if (h == lim) return;
	vector<vector<Mint>> dp(3, vector<Mint>(3));
	dp[0][0] = 1;
	for (int y : E[x]) {
		if (y == p) continue;
		go(y, x, h + 1);
		vector<vector<Mint>> ndp(3, vector<Mint>(3));
		for (int a = 0; a < 3; ++a)
			for (int b = 0; b < 3; ++b) {
				for (int aa = 0; aa < 3; ++aa)
					for (int bb = 0; bb < 3; ++bb) {
						ndp[min(a + aa, 2)][b] += dp[a][b] * F[y][aa][bb];
						ndp[a][min(b + bb, 2)] += dp[a][b] * F[y][aa][bb];
						ndp[a][b] += dp[a][b] * F[y][aa][bb];
					}
				if (h + 1 == lim) {
					ndp[min(a + 1, 2)][b] += dp[a][b];
					ndp[a][min(b + 1, 2)] += dp[a][b];
					ndp[a][b] += dp[a][b];
				}
			}
		swap(dp, ndp);
	}
	for (int a = 0; a < 3; ++a)
		for (int b = 0; b < 3; ++b)
			F[x][a][b] = dp[a][b];
}
int pv[MAXN];
int mxh, mxv;
void dfs(int x, int p = -1, int h = 0) {
	if (h > mxh) {
		mxh = h;
		mxv = x;
	}
	for (int y : E[x]) {
		if (y == p) continue;
		pv[y] = x;
		dfs(y, x, h + 1);
	}
}
int main() {
	int n;
	scanf("%d", &n);
	for (int i = 1; i < n; ++i) {
		int a, b;
		scanf("%d%d", &a, &b);
		E[a].push_back(b);
		E[b].push_back(a);
	}
	mxh = -1;
	dfs(1);
	mxh = -1;
	int diam1 = mxv;
	dfs(mxv);
	int diam2 = mxv;
	vector<int> path;
	for (int i = diam2;; i = pv[i]) {
		path.push_back(i);
		if (i == diam1) break;
	}
	if (mxh % 2 == 0) {
		lim = mxh / 2;
		int cen = path[lim];
		go(cen);
		assert(F[cen][0][1] == F[cen][1][0]);
		assert(F[cen][0][2] == F[cen][2][0]);
		Mint ans = F[cen][1][1] / 2;
		printf("%d\n", ans.val);
	} else {
		lim = mxh / 2;
		int cen1 = path[lim], cen2 = path[lim + 1];
		go(cen1, cen2);
		Mint ans = F[cen1][1][0] + F[cen1][1][1] + F[cen1][1][2];
		memset(F, 0, sizeof(F));
		go(cen2, cen1);
		ans *= F[cen2][0][1] + F[cen2][1][1] + F[cen2][2][1];
		printf("%d\n", ans.val);
	}
}