小红的魔法树探险_

$\hspace{15pt}$ 小红在神秘森林中发现一棵魔法树，树有 $n$ 个节点（编号 $1$ 到 $n$ ），由 $n - 1$ 条无向边连接成树状。她从 $1$ 号节点注入魔力（ $1$ 号节点默认激活），随后魔力从 $1$ 号节点开始，每一步从当前所在节点出发，从它的所有邻点中等概率（独立）选择一个并沿该边移动到该邻点。
$\hspace{15pt}$ 若魔力到达未激活节点则激活它并继续流动，若到达已激活节点则魔力消散。
$\hspace{15pt}$ 求魔力消散时已经被激活的节点数量的期望值。

$\hspace{15pt}$ 可以证明答案可以表示为一个不可约分数 $\tfrac{p}{q}$ ，为了避免精度问题，请直接输出整数 $\left(p \times q^{-1} \bmod M\right)$ 作为答案，其中 $M = (10^9+7)$ ， $q^{-1}$ 是满足 $q\times q^{-1} \equiv 1 \pmod{M}$ 的整数。更具体地，你需要找到一个整数 $x \in [0, M)$ 满足 $x \times q$ 对 $M$ 取模等于 $p$ ，您可以查看样例解释得到更具体的说明。

说明

在这个样例中，树为  的链。从节点  开始，魔力到节点  使其激活。在节点  时，有  概率到已激活的节点 ，此时激活  个节点；有  概率到节点  使其激活，之后魔力消散，此时激活  个节点。期望为 。

我们能够找到，，对  取模后恰好等于分子 ，所以  是需要输出的答案。

小红的魔法树探险

输入描述:

输出描述:

输入

输出

说明

输入

输出

输入

输出

问题信息

热门推荐

相关试题