Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
D. Stranger Trees

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputWill shares a psychic connection with the Upside Down Monster, so everything the monster knows, Will knows. Suddenly, he started drawing, page after page, non-stop. Joyce, his mom, and Chief Hopper put the drawings together, and they realized, it's a labeled tree!

A tree is a connected acyclic graph. Will's tree has *n* vertices. Joyce and Hopper don't know what that means, so they're investigating this tree and similar trees. For each *k* such that 0 ≤ *k* ≤ *n* - 1, they're going to investigate all labeled trees with *n* vertices that share exactly *k* edges with Will's tree. Two labeled trees are different if and only if there's a pair of vertices (*v*, *u*) such that there's an edge between *v* and *u* in one tree and not in the other one.

Hopper and Joyce want to know how much work they have to do, so they asked you to tell them the number of labeled trees with *n* vertices that share exactly *k* edges with Will's tree, for each *k*. The answer could be very large, so they only asked you to tell them the answers modulo 1000000007 = 10^{9} + 7.

Input

The first line of input contains a single integer *n* (2 ≤ *n* ≤ 100) — the size of the tree.

The next *n* - 1 lines contain the edges of Will's tree. Each line contains two integers *v* and *u* (1 ≤ *v*, *u* ≤ *n*, *v* ≠ *u*), endpoints of an edge. It is guaranteed that the given graph is a tree.

Output

Print *n* integers in one line. *i*-th integer should be the number of the number of labeled trees with *n* vertices that share exactly *i* - 1 edges with Will's tree, modulo 1000 000 007 = 10^{9} + 7.

Examples

Input

3

1 2

1 3

Output

0 2 1

Input

4

1 2

2 3

3 4

Output

1 7 7 1

Input

4

1 2

1 3

1 4

Output

0 9 6 1

Codeforces (c) Copyright 2010-2022 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/23/2022 08:35:17 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|