問題文

$N$ 頂点からなる木が与えられます。頂点には $1$ から $N$ までの番号がついており、$i$ 番目の辺は頂点 $a_i$ と $b_i$ を結んでいます。

正整数列 $P = (P_1, P_2, \\ldots, P_N)$ であって、以下の条件を満たすものの個数を $998244353$ で割った余りを求めてください。

• $1\\leq P_i\\leq N$
• $i\\neq j$ ならば $P_i\\neq P_j$
• $1\\leq a, b, c\\leq N$ に対して頂点 $a$ と 頂点 $b$、頂点 $b$ と頂点 $c$ がともに隣接しているならば、$P_a < P_b > P_c$ または $P_a > P_b < P_c$ が成り立つ。

制約

• $2\\leq N\\leq 3000$
• $1\\leq a_i, b_i\\leq N$
• 入力されるグラフは木である

入力

入力は以下の形式で標準入力から与えられます。

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

出力

答えを出力してください。

入力例 1

3
1 2
2 3

出力例 1

4

条件を満たす $P$ は以下の $4$ 通りです。

• $P = (1, 3, 2)$
• $P = (2, 1, 3)$
• $P = (2, 3, 1)$
• $P = (3, 1, 2)$

入力例 2

4
1 2
1 3
1 4

出力例 2

12

入力例 3

6
1 2
2 3
3 4
4 5
5 6

出力例 3

122

入力例 4

9
8 5
9 8
1 9
2 5
6 1
7 6
3 8
4 1

出力例 4

19080