配点 : $600$ 点

問題文

$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}$

出力

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

3
1 2
2 3

4

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

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

4
1 2
1 3
1 4

12

6
1 2
2 3
3 4
4 5
5 6

122

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

19080