题目背景

如果你不清楚本题的某些定义，可以阅读【说明/提示】部分。

题目描述

有一棵包含 $n$ 个节点的树 $T$，它的所有边依次编号为 $1$ 至 $n-1$。

保证对于 $T$ 中任意一个节点 $u$ ，从 $u$ 到 $n$ 号节点的简单路径都不经过任何编号小于 $u$ 的节点。

按照如下步骤生成一张包含 $n$ 个节点的无向图 $G$：

选取一个 $1 \sim n-1$ 的排列 $p$，然后依次进行 $n-1$ 次操作。在进行第 $i$ 次操作时，首先删除树 $T$ 中编号为 $p_i$ 的边 $(a,b)$，然后，记 $u$ 和 $v$ 分别为当前树 $T$ 中与 $a,b$ 联通的所有点中，编号最大的点，并在图 $G$ 的 $u$ 号点和 $v$ 号点之间连一条边。

求对于给定的树 $T$，按上述方式一共可以生成多少种本质不同的图 $G$。图 $G_1$ 和 $G_2$ 本质不同当且仅当存在 $u$ 和 $v$ 满足在 $G_1$ 中不存在边 $(u,v)$，而 $G_2$ 中存在。

因为答案可能很大，你只需要求出答案对 $998244353$ 取模的值。

输入格式

第一行一个整数 $n$，表示树 $T$ 中的节点数量。

接下来 $n-1$ 行，第 $i$ 行两个整数 $u,v$，表示在 $T$ 中编号为 $i$ 的边是 $(u,v)$。

输出格式

一行一个整数，答案对 $998244353$ 取模的值。

4
1 4
2 3
3 4

2

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

4605

提示

【帮助与提示】

为方便选手测试代码，本题额外提供一组附加样例供选手使用。

样例输入 样例输出

---

【样例解释】

样例一中可能生成的图 $G$ 如图所示：

当 $p = \{1,2,3\},\{2,1,3\},\{2,3,1\}$ 时将生成右侧的图，否则将生成左侧的图。

对于样例二，我有一个绝妙的解释，只可惜这里空白的位置太小，写不下。

---

【数据范围】

本题采用捆绑测试。

对于全部数据，保证 $1 \leq n \leq 3 \times 10^3$，$1 \leq u,v \leq n$。

保证，输入的边形成一棵树，且对于任意一个节点 $u$ ，从 $u$ 到 $n$ 号节点的简单路径都不经过任何编号小于 $u$ 的节点。

子任务编号	$n\leq$	特殊性质	分值
Subtask 1	$5$	无	$32$
Subtask 2	$14$		$16$
Subtask 3	$10^3$	所有节点都与 $n$ 号点直接相连	$1$
Subtask 4		树的形态是一条链	$7$
Subtask 5	$50$	无	$22$
Subtask 6	$3 \times 10^3$

---

下面是本题用到的一些定义：

• 一棵树是一张有 $n$ 个节点，$n-1$ 条边的无向连通图。

• 边 $(u,v)$ 表示连接点 $u$ 和点 $v$ 的一条边。

• 一条路径是一个序列 $p_1,p_2 \ldots p_k$ ，满足对于任意 $1 \leq i < k$，边 $(p_i,p_{i+1})$ 都存在于 $T$ 中，且 没有被之前的操作删除。

• 点 $u$ 和 $v$ 联通当且仅当存在一条路径 $p_1,p_2 \ldots p_k$ 满足 $p_1=u$ 且 $p_k=v$。任何一个点都和自己联通。