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

你需要用 $N$ 种不同的颜色为所有节点染色。颜色用 $1$ 到 $N$ 的整数表示。如果可以通过重复执行以下操作 $N - 1$ 次，将所有节点染成同一种颜色，则称该染色方案是“好的”：

• 选择一对颜色 $(A, B)$，使得 $|A - B| = 1$，且存在一条边连接一个颜色为 $A$ 的节点和一个颜色为 $B$ 的节点。
• 将所有当前颜色为 $A$ 的节点的颜色更改为 $B$。

你的任务是计算好的染色方案的数量，结果对 $998\,244\,353$ 取模。

输入格式

第一行包含一个整数 $N$，表示节点数 ($2 \le N \le 2000$)。

接下来的 $N - 1$ 行，每行包含两个整数 $u_i$ 和 $v_i$，描述树的一条边 ($1 \le u_i, v_i \le N$)。

保证给定的图是一棵树。

输出格式

输出一行，表示好的染色方案数量，结果对 $998\,244\,353$ 取模。

样例

样例输入 1

4
1 2
2 3
3 4

样例输出 1

16

样例输入 2

4
1 2
1 3
1 4

样例输出 2

24