{"raw_statement":[{"iden":"problem statement","content":"There is a tree with $N$ vertices numbered from $1$ to $N$, where the $i$\\-th edge connects vertices $A_i$ and $B_i$.\nWe will now randomly write real numbers between $-(N-1)$ and $1$ (inclusive) on each vertex of this tree. The random number distributions are all independent uniform distributions.\nThen, the **score** of the tree is defined as follows:\n\n*   For each vertex $i$, define $x_i$ as follows:\n    *   The maximum value of the sum of values written on vertices of connected subgraphs that contain vertex $i$\n*   If there exists $i$ that does not satisfy $0 \\leq x_i \\leq 1$, the tree's score is $0$.\n*   Otherwise, the tree's score is $\\prod_{1 \\leq i \\leq N} x_i$.\n\nFind the expected value $\\text{mod }{998244353}$ of the tree's score.\nDefinition of expected value $\\text{mod }{998244353}$It can be proved that the sought expected value is always a rational number. Also, under the constraints of this problem, it can be proved that when the value is expressed as an irreducible fraction $\\frac{P}{Q}$, we have $Q \\neq 0 \\pmod{998244353}$. Therefore, an integer $R$ satisfying $R \\times Q \\equiv P \\pmod{998244353}, 0 \\leq R < 998244353$ is uniquely determined. Answer this $R$."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 5000$\n*   $1 \\leq A_i, B_i \\leq N$\n*   The input graph is a tree."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$\n$A_1$ $B_1$\n$A_2$ $B_2$\n$\\vdots$\n$A_{N-1}$ $B_{N-1}$"},{"iden":"sample input 1","content":"1"},{"iden":"sample output 1","content":"499122177\n\nThe expected value of the score is $1/2$."},{"iden":"sample input 2","content":"2\n1 2"},{"iden":"sample output 2","content":"873463809\n\nThe expected value of the score is $1/8$."},{"iden":"sample input 3","content":"3\n1 2\n2 3"},{"iden":"sample output 3","content":"842653798\n\nThe expected value of the score is $13/648$."},{"iden":"sample input 4","content":"5\n1 2\n2 3\n3 4\n4 5"},{"iden":"sample output 4","content":"132050425\n\nThe expected value of the score is $41/187500$."},{"iden":"sample input 5","content":"8\n1 2\n1 3\n1 4\n1 5\n5 6\n5 7\n5 8"},{"iden":"sample output 5","content":"243711918\n\nThe expected value of the score is $2477/30064771072$."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}