AT_agc073_c [AGC073C] Product of Max of Sum of Subtree

There is a tree with $ N $ vertices numbered from $ 1 $ to $ N $ , where the $ i $ -th edge connects vertices $ A_i $ and $ B_i $ . We 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. Then, the **score** of the tree is defined as follows: - For each vertex $ i $ , define $ x_i $ as follows: - The maximum value of the sum of values written on vertices of connected subgraphs that contain vertex $ i $ - If there exists $ i $ that does not satisfy $ 0 \leq x_i \leq 1 $ , the tree's score is $ 0 $ . - Otherwise, the tree's score is $ \prod_{1 \leq i \leq N} x_i $ . Find the expected value $ \text{mod }{998244353} $ of the tree's score. Definition 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 $ .

The input is given from Standard Input in the following format: > $ N $ $ A_1 $ $ B_1 $ $ A_2 $ $ B_2 $ $ \vdots $ $ A_{N-1} $ $ B_{N-1} $

Output the answer.

### Sample Explanation 1 The expected value of the score is $ 1/2 $ . ### Sample Explanation 2 The expected value of the score is $ 1/8 $ . ### Sample Explanation 3 The expected value of the score is $ 13/648 $ . ### Sample Explanation 4 The expected value of the score is $ 41/187500 $ . ### Sample Explanation 5 The expected value of the score is $ 2477/30064771072 $ . ### Constraints - $ 1 \leq N \leq 5000 $ - $ 1 \leq A_i, B_i \leq N $ - The input graph is a tree.