{"raw_statement":[{"iden":"problem statement","content":"For an undirected tree $t$, let us define a rational number $f(t)$ as follows.\n\n*   Let $n$ be the number of vertices in $t$.\n*   If $n=1$: Let $f(t)=1$.\n*   If $n \\geq 2$:\n    *   For an edge $e$ in $t$, we denote by $t_x(e)$ and $t_y(e)$ the two trees that result from deleting $e$ from $t$ (in arbitrary order).\n    *   Let $f(t)=(\\sum_{e \\in t} f(t_x(e)) \\times f(t_y(e)))/n$.\n\nYou are given a tree $T$ with $N$ vertices numbered $1$ to $N$. The $i$\\-th edge connects Vertex $A_i$ and Vertex $B_i$.\nFind the value $f(T)$ $\\text{mod }{998244353}$.\nWhat is a rational number $\\text{mod }{998244353}$?Under the Constraints of this problem, when the sought rational number is represented as $\\frac{P}{Q}$, it can be proved that $Q \\neq 0 \\pmod{998244353}$. Therefore, there is a unique integer $R$ such that $R \\times Q \\equiv P \\pmod{998244353}, 0 \\leq R < 998244353$. Find this $R$."},{"iden":"constraints","content":"*   $2 \\leq N \\leq 5000$\n*   $1 \\leq A_i,B_i \\leq N$\n*   The given graph is a tree."},{"iden":"input","content":"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":"2\n1 2"},{"iden":"sample output 1","content":"499122177\n\nWe have $f(T)=1/2$."},{"iden":"sample input 2","content":"3\n1 2\n2 3"},{"iden":"sample output 2","content":"332748118\n\nWe have $f(T)=1/3$."},{"iden":"sample input 3","content":"4\n1 2\n2 3\n3 4"},{"iden":"sample output 3","content":"103983787"},{"iden":"sample input 4","content":"10\n4 5\n1 9\n6 1\n8 4\n5 9\n4 7\n3 10\n5 2\n4 3"},{"iden":"sample output 4","content":"462781191"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}