Problem Description

You are given a tree with $ N $ vertices numbered $1,\ \ldots,\ N$. There are $ N-1 $ edges numbered $1,\ \ldots,\ N-1$, where edge $ i $ connects vertices $ a_i $ and $ b_i $.

Niwango performs $ N-1 $ operations. The $ i $-th operation consists of the following steps:

• Choose an edge of the tree with equal probability (let the chosen edge be $ e $ and its endpoints be $ u $ and $ v $).
• Gain $ xy $ points, where $ x $ is the degree of $ u $ and $ y $ is the degree of $ v $.
• Remove $ e $ and merge $ u $ and $ v $ into a single vertex (i.e., perform edge contraction).

Find the remainder when the expected total score Niwango gains after $ N-1 $ operations is multiplied by $ (N-1)! $ (this can be shown to be an integer) and divided by $ 998244353 $.

Input Format

The input is given from the standard input in the following format:

$ N $ $ a_1 $ $ b_1 $ $\vdots$ $ a_{N-1} $ $ b_{N-1} $

Output Format

Output the answer.

Sample Input and Output

Sample Input #1

6
1 4
1 2
1 3
4 5
4 6

Sample Output #1

1640

Sample Input #2

3
1 2
2 3

Sample Output #2

6

Sample Input #3

20
12 10
12 14
12 9
17 9
1 17
1 2
11 2
11 15
13 11
13 4
5 1
20 5
3 4
16 11
3 18
17 8
20 7
6 3
19 2

Sample Output #3

253636877

Notes/Hints

Constraints

• $2\ \leq\ N\ \leq\ 10^{5}$
• $1\ \leq\ a_i,\ b_i\ \leq\ N$
• The given graph is a tree

Sample Explanation 1

• For example, if edge $ 1 $ is chosen in the first operation, you gain $ 9 $ points and the graph changes as shown in the following figure:

Sample Explanation 3

• Find the remainder when the answer is divided by $ 998244353 $.

见题面 Input 部分

见题面 Output 部分