题目描述

有一棵包含 $N$ 个节点的树，节点编号从 $1$ 到 $N$。对于每个 $i = 1, \ldots, N - 1$，第 $i$ 条边连接节点 $u_i$ 和节点 $v_i$。

你需要给所有节点涂上不同的颜色。颜色用 $1$ 到 $N$ 之间的整数表示。

如果能够重复完成以下操作 $N - 1$ 次，则称树上的颜色分配是良好的：

• 选择一对颜色 $(A, B)$，满足以下两个条件：
  • $|A - B| = 1$。
  • 存在一条边连接一个涂有颜色 $A$ 的节点和一个涂有颜色 $B$ 的节点。
• 将所有当前涂有颜色 $A$ 的节点的颜色改为颜色 $B$。

你的任务是计算树上良好颜色分配的数量，结果对 $998,244,353$ 取模。

输入格式

输入包含一个单独的测试用例，格式如下：

$$\begin{aligned} &N \\ &u_1 \ v_1 \\ &u_2 \ v_2 \\ &\vdots \\ &u_{N-1} \ v_{N-1} \end{aligned}$$

第一行包含一个整数 $N$，满足 $1 \leq N \leq 2,000$。接下来的 $N - 1$ 行，每行包含两个整数 $u_i, v_i$，满足 $1 \leq u_i, v_i \leq N$。保证给定的图是一棵树。

输出格式

输出一行，表示给定树上良好颜色分配的数量，结果对 $998,244,353$ 取模。

输入输出样例 #1

输入 #1

4
1 2
2 3
3 4

输出 #1

16

输入输出样例 #2

输入 #2

4
1 2
1 3
1 4

输出 #2

24

说明/提示

翻译由 DeepSeek V3.2 完成