Migrated from Lutece 3250 数树

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

给定 $n$ 个点的完全图 $G$，以及其一棵生成树 $T$。求 $G$ 有多少棵生成树 $T'$，满足 $T'$ 和 $T$ 的交集恰好包含 $k$ 条边。对每个 $i\in[0,n-1]$ 依次求出答案。答案对 $10^9+7$ 取模。

Input

第一行，一个正整数，表示 $n$。

接下来 $n-1$ 行，描述一棵树。

Output

一行，共 $n$ 个正整数，用空格隔开，表示答案。

Samples

4
2 1
3 2
4 2

0 9 6 1

Constraints

$2\leq n \leq 100$

Resources

2024 UESTC ICPC Training for Math