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:
// I think of what the world could be, A vision of the one I see, A million dreams is all it's gonna take

#include<bits/stdc++.h>

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

const int maxn = 2e5 + 10, mod = 998244353;

int h[maxn], par[maxn];
vector<int> v[maxn];

pii far(int u, int pr = -1){
    par[u] = pr;
    h[u] = pr == -1 ? 0 : (h[pr] + 1);
    pii ans = {0, u};
    for(int y : v[u]){
	if(y != pr){
	    pii p = far(y, u);
	    p.F++;
	    ans = max(ans, p);
	}	    
    }
    return ans;
}

int total[maxn], dp1[maxn], dp2[maxn], under[maxn];

void dfs(int u, int par = -1){
    total[u] = 1, dp2[u] = 1;
    if(sz(v[u]) == (par != -1))
	dp2[u] = 0, dp1[u] = 1;
    for(int y : v[u]){
	if(y != par){
	    dfs(y, u);
	    under[u] = max(under[u], under[y] + 1);
	    total[u] = 3ll * total[u] * total[y] % mod;
	}
    }
    for(int y : v[u]){
	if(y != par){
	    int no = 0, yes = 0;
	    if(under[u] == under[y] + 1){
		no = (2ll * total[y] + 1ll * dp2[y]) % mod;
		yes = dp1[y];
	    }
	    else{
		no = 3ll * total[y] % mod;
		yes = 0;
	    }
	    dp1[u] = (1ll * dp1[u] * no + 1ll * dp2[u] * yes) % mod;
	    dp2[u] = (1ll * dp2[u] * no) % mod;
	}
    }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie();

    int n;
    cin >> n;
    for(int i = 0; i < n-1; i++){
	int a, b;
	cin >> a >> b;
	v[a].PB(b);
	v[b].PB(a);
    }
    int A = far(1).S;
    pii p = far(A);
    int diam = p.F, B = p.S;

    int ans = 0;

    if(diam & 1){
	for(int i = 0; i < (diam/2); i++)
	    B = par[B];
	A = par[B];
	dfs(A, B);
	dfs(B, A);
	ans = 1ll * dp1[A] * dp1[B] % mod;
    }
    else{
	for(int i = 0; i < (diam/2); i++)
	    B = par[B];
	dfs(B);
	int zer = 1, one = 0, two = 0; 
	for(int y : v[B]){
	    int yes = 0, no = 0;
	    if(under[B] == under[y] + 1){
		no = (1ll * total[y] + 2ll * dp2[y]) % mod;
		yes = dp1[y];
	    }
	    else{
		no = 3ll * total[y] % mod;
	    }
	    two = (1ll * two * no + 1ll * one * yes) % mod;
	    one = (1ll * one * no + 1ll * zer * yes) % mod;
	    zer = (1ll * zer * no) % mod;
	}
	ans = two;
    }
    return cout << ans << endl, 0;
}