题目描述

给定一个包含 $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

满足条件的 $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