AT_abc207_f.[ABC207F] Tree Patrolling

有一棵包含 $N$ 个顶点的树，每个顶点编号为 $1$ 到 $N$。第 $i$ 条边连接了顶点 $u_i$ 和顶点 $v_i$，且为双向边。

你作为这棵树的主人，打算在若干个顶点（可以为 $0$ 个）上选择放置高桥君，让他来守卫这棵树。被放置在顶点 $x$ 的高桥君会守卫顶点 $x$ 以及所有与 $x$ 直接通过边相连的顶点。

选择放置高桥君的顶点的方式共有 $2^N$ 种。在这些方式中，有多少种方式使得被至少一位高桥君守卫的顶点恰好有 $K$ 个？

请对于 $K=0,1,\ldots,N$，分别输出答案，并对 $10^9+7$ 取模。

输入以如下格式从标准输入读入。

$N$
$u_1$ $v_1$
$u_2$ $v_2$
$\hspace{0.6cm}\vdots$
$u_{N-1}$ $v_{N-1}$

请输出 $N+1$ 行。第 $i$ 行输出当 $K=i-1$ 时的答案。

限制条件

• $1 \leq N \leq 2000$
• $1 \leq u_i < v_i \leq N$
• 给定的图为一棵树
• 输入均为整数

样例说明 1

放置高桥君的顶点选择方式共有如下 $8$ 种：

• 不在任何顶点放置高桥君。此时所有顶点都未被守卫。
• 只在顶点 $1$ 放置高桥君。此时所有顶点都被守卫。
• 只在顶点 $2$ 放置高桥君。此时顶点 $1$ 和 $2$ 共 $2$ 个顶点被守卫。
• 只在顶点 $3$ 放置高桥君。此时顶点 $1$ 和 $3$ 共 $2$ 个顶点被守卫。
• 在顶点 $1$ 和顶点 $2$ 放置高桥君。此时所有顶点都被守卫。
• 在顶点 $1$ 和顶点 $3$ 放置高桥君。此时所有顶点都被守卫。
• 在顶点 $2$ 和顶点 $3$ 放置高桥君。此时所有顶点都被守卫。
• 在所有顶点都放置高桥君。此时所有顶点都被守卫。

由 ChatGPT 4.1 翻译