#P1517F. Reunion

    ID: 5894 Type: RemoteJudge 3000ms 256MiB Tried: 0 Accepted: 0 Difficulty: (None) Uploaded By: Tags>combinatoricsdptrees*3200

Reunion

No submission language available for this problem.

Description

It is reported that the 2050 Conference will be held in Yunqi Town in Hangzhou from April 23 to 25, including theme forums, morning jogging, camping and so on.

The relationship between the nn volunteers of the 2050 Conference can be represented by a tree (a connected undirected graph with nn vertices and n1n-1 edges). The nn vertices of the tree corresponds to the nn volunteers and are numbered by 1,2,,n1,2,\ldots, n.

We define the distance between two volunteers ii and jj, dis(i,j)(i,j) as the number of edges on the shortest path from vertex ii to vertex jj on the tree. dis(i,j)=0(i,j)=0 whenever i=ji=j.

Some of the volunteers can attend the on-site reunion while others cannot. If for some volunteer xx and nonnegative integer rr, all volunteers whose distance to xx is no more than rr can attend the on-site reunion, a forum with radius rr can take place. The level of the on-site reunion is defined as the maximum possible radius of any forum that can take place.

Assume that each volunteer can attend the on-site reunion with probability 12\frac{1}{2} and these events are independent. Output the expected level of the on-site reunion. When no volunteer can attend, the level is defined as 1-1. When all volunteers can attend, the level is defined as nn.

The first line contains a single integer nn (2n3002\le n\le 300) denoting the number of volunteers.

Each of the next n1n-1 lines contains two integers aa and bb denoting an edge between vertex aa and vertex bb.

Output the expected level modulo 998244353998\,244\,353.

Formally, let M=998244353M = 998\,244\,353. It can be shown that the answer can be expressed as an irreducible fraction pq\frac{p}{q}, where pp and qq are integers and q≢0(modM)q \not \equiv 0 \pmod{M}. Output the integer equal to pq1modMp \cdot q^{-1} \bmod M. In other words, output such an integer xx that 0x<M0 \le x < M and xqp(modM)x \cdot q \equiv p \pmod{M}.

Input

The first line contains a single integer nn (2n3002\le n\le 300) denoting the number of volunteers.

Each of the next n1n-1 lines contains two integers aa and bb denoting an edge between vertex aa and vertex bb.

Output

Output the expected level modulo 998244353998\,244\,353.

Formally, let M=998244353M = 998\,244\,353. It can be shown that the answer can be expressed as an irreducible fraction pq\frac{p}{q}, where pp and qq are integers and q≢0(modM)q \not \equiv 0 \pmod{M}. Output the integer equal to pq1modMp \cdot q^{-1} \bmod M. In other words, output such an integer xx that 0x<M0 \le x < M and xqp(modM)x \cdot q \equiv p \pmod{M}.

Samples

Sample Input 1

3
1 2
2 3

Sample Output 1

499122177

Sample Input 2

5
1 2
2 3
3 4
3 5

Sample Output 2

249561089

Sample Input 3

10
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10

Sample Output 3

821796866

Note

For the first example, the following table shows all possible outcomes. yesyes means the volunteer can attend the on-site reunion and nono means he cannot attend. 123levelyesyesyes3yesyesno1yesnoyes0yesnono0noyesyes1noyesno0nonoyes0nonono1\begin{array}{cccc} 1 & 2 & 3 & level\\ yes & yes & yes & 3\\ yes & yes & no & 1\\ yes & no & yes & 0\\ yes & no & no & 0\\ no & yes & yes & 1\\ no & yes & no & 0\\ no & no & yes & 0\\ no & no & no & -1\\ \end{array} The expected level is 3+1+1+(1)23=12\frac{3+1+1+(-1)}{2^3}=\frac{1}{2}.