{"raw_statement":[{"iden":"problem statement","content":"Given is a tree with $N$ vertices. The vertices are numbered $1$ to $N$, and the $i$\\-th edge connects Vertices $a_i$ and $b_i$.\nFind the number of sequences of positive integers $P = (P_1, P_2, \\ldots, P_N)$ that satisfy the conditions below, modulo $998244353$.\n\n*   $1\\leq P_i\\leq N$\n*   $P_i\\neq P_j$ if $i\\neq j$.\n*   For $1\\leq a, b, c\\leq N$, if Vertices $a$ and $b$ are adjacent, and Vertices $b$ and $c$ are also adjacent, $P_a < P_b > P_c$ or $P_a > P_b < P_c$ holds."},{"iden":"constraints","content":"*   $2\\leq N\\leq 3000$\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":"3\n1 2\n2 3"},{"iden":"sample output 1","content":"4\n\nThe $4$ sequences satisfying the conditions are:\n\n*   $P = (1, 3, 2)$\n*   $P = (2, 1, 3)$\n*   $P = (2, 3, 1)$\n*   $P = (3, 1, 2)$"},{"iden":"sample input 2","content":"4\n1 2\n1 3\n1 4"},{"iden":"sample output 2","content":"12"},{"iden":"sample input 3","content":"6\n1 2\n2 3\n3 4\n4 5\n5 6"},{"iden":"sample output 3","content":"122"},{"iden":"sample input 4","content":"9\n8 5\n9 8\n1 9\n2 5\n6 1\n7 6\n3 8\n4 1"},{"iden":"sample output 4","content":"19080"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}