https://www.luogu.com.cn/paste/0jtzo946

# 仓鼠找sugar II

## 题目描述

小仓鼠的和他的基（mei）友（zi）sugar 住在地下洞穴中，每个节点的编号为 $1$ ~ $n$。地下洞穴是一个树形结构。这一天小仓鼠打算从从他的卧室（$a$，是任意的）他的基友卧室（$b$，还是任意的）。（注意，$a$ 有可能等于 $b$。）然而小仓鼠学 OI 学傻了，不知道怎么怎么样才能最短的走到目的地。于是他只能随便乱走。当他在每一个节点时，等概率到这个点的母亲或者所有孩子节点（例如这个节点有一个母亲节点和两个子节点，那么下一步走到这 $3$ 个节点的概率都是 $\frac{1}{3}$）。一但走到了他基友的卧室，就会停下。

现在小仓鼠希望知道，他走到目的地时，走的步数的期望。这个期望本来是一个有理数，但是为了避免误差，我们要求对这个有理数取模，$\bmod 998244353$。

下面是“分数”模运算的定义：

$$\because \gcd(b,m)=1$$


$$\therefore k \equiv \frac{a}{b} (\bmod m) \to kb \equiv a (\bmod m)$$

这里求 
$$x \equiv \frac{1}{17}(\bmod 2668)$$
$$\to 17x \equiv 1 (\bmod 2668)$$
$$\to 17x = 2668k + 1 (k∈\mathbb Z)$$

取合适的 $k$ 使得 $17\mid(2668k+1)$。

这里刚好 $17\mid(2668k+1)$，

所以 $k = 1, x = \frac{(2668+1)}{17} = 157$。


当然，当 $k = 1 + 17n$ 时，

$x = \frac{2668 + 17\times n\times 2668 + 1}{17} = 157 + 2668n$，

也符合条件（$n\in\mathbb Z$）。


但如果限定 $2668 > x > 0$，$x$ 是唯一的。



小仓鼠那么弱，还要天天被 JOHNKRAM 大爷虐，请你快来救救他吧！

## 输入格式

第一行一个正整数 $n$，表示这棵树节点的个数。

接下来 $n-1$ 行，每行两个正整数 $u$ 和 $v$，表示节点 $u$ 到节点 $v$ 之间有一条边。

## 输出格式

一个整数，表示取模后的答案。

## 样例 #1

### 样例输入 #1

\```
3
1 2
1 3
\```

### 样例输出 #1

\```
110916041
\```

## 提示

对于 $30\%$ 的数据 $n\leq5$；

对于 $50\%$ 的数据 $n\leq5000$；

对于所有数据 $n\leq100000$；

样例解释

期望是 $16/9$。

如果 $a$ 在叶子 $b$ 在根，$E_1=1$。有 $2$ 种情况。

如果 $a$ 在根，$b$ 在叶子。$E_2=1/2+3\times1/4+5\times1/8...=3$。有 $2$ 种情况。

如果 $a$ 和 $b$ 都在不同的叶子，$E_3=E_2+1$。有 $2$ 种情况。

如果 $a=b$，$E_4=0$，有$3$种情况。

所以期望是 $16/9$，有理数取模后就是输出。