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;

int read(){
	int a = 0; char c = getchar(); while(!isdigit(c)) c = getchar();
	while(isdigit(c)){a = a * 10 + c - 48; c = getchar();} return a;
}

const int _ = 2e5 + 7 , MOD = 998244353 , iv2 = (MOD + 1) / 2;
struct Edge{int end , upEd;}Ed[_ << 1];
int dp[_][3][3] , N , cntEd , head[_];
void addEd(int a , int b){Ed[++cntEd] = (Edge){b , head[a]}; head[a] = cntEd;}

int mx , id , pre[_];
void dfs1(int x , int p , int l){
	pre[x] = p; if(l > mx){mx = l; id = x;}
	for(int i = head[x] ; i ; i = Ed[i].upEd)
		if(Ed[i].end != p) dfs1(Ed[i].end , x , l + 1);
}

int mxdep[_];
void dfs2(int x , int p){
	for(int i = head[x] ; i ; i = Ed[i].upEd)
		if(Ed[i].end != p){dfs2(Ed[i].end , x); mxdep[x] = max(mxdep[x] , mxdep[Ed[i].end] + 1);}
}

void DP(int x , int p){
	dp[x][0][0] = 1; bool flg = 0;
	for(int i = head[x] ; i ; i = Ed[i].upEd)
		if(Ed[i].end != p){
			flg = 1; DP(Ed[i].end , x); static int tmp[3][3]; memset(tmp , 0 , sizeof(tmp));
			for(int j = 0 ; j < 3 ; ++j)
				for(int k = 0 ; k < 3 ; ++k)
					for(int p = 0 ; p < 3 ; ++p)
						for(int q = 0 ; q < 3 ; ++q){
							int coef = 3;
							if(mxdep[Ed[i].end] + 1 == mxdep[x]){
								tmp[min(j + p , 2)][k] = (tmp[min(j + p , 2)][k] + 1ll * dp[x][j][k] * dp[Ed[i].end][p][q]) % MOD;
								tmp[j][min(k + q , 2)] = (tmp[j][min(k + q , 2)] + 1ll * dp[x][j][k] * dp[Ed[i].end][p][q]) % MOD;
								coef -= 2;
							}
							tmp[j][k] = (tmp[j][k] + 1ll * coef * dp[x][j][k] * dp[Ed[i].end][p][q]) % MOD;
						}
			memcpy(dp[x] , tmp , sizeof(tmp));
		}
	if(!flg){dp[x][0][0] = 0; dp[x][1][1] = 1;}
}

int main(){
	N = read(); for(int i = 1 ; i < N ; ++i){int x = read() , y = read(); addEd(x , y); addEd(y , x);}
	dfs1(1 , 0 , 0); mx = 0; int t = id; dfs1(t , 0 , 0);
	for(int i = 0 ; i < mx / 2 ; ++i) id = pre[id];
	if(mx & 1){
		dfs2(id , pre[id]); DP(id , pre[id]); dfs2(pre[id] , id); DP(pre[id] , id); int sum = 0;
		for(int i = 0 ; i < 3 ; ++i)
			for(int j = 0 ; j < 3 ; ++j)
				for(int k = 0 ; k < 3 ; ++k)
					for(int l = 0 ; l < 3 ; ++l){
						if(i == 1 && l == 1) sum = (sum + 1ll * dp[id][i][j] * dp[pre[id]][k][l]) % MOD;
						if(j == 1 && k == 1) sum = (sum + 1ll * dp[id][i][j] * dp[pre[id]][k][l]) % MOD;
					}
		printf("%lld\n" , 1ll * sum * iv2 % MOD);
	}else{dfs2(id , 0); DP(id , 0); printf("%lld\n" , 1ll * iv2 * dp[id][1][1] % MOD);}
	return 0;
}