The black cat's world is coming to an end.

In this world that is coming to an end, Liki and Sasami need to find the truth of the world. Specifically, this world can be viewed as a rooted tree with $n$ nodes, where the root is node 1. Furthermore, there exists a depth-first search (DFS) traversal of the tree such that the $i$-th visited node is $i$. In other words, $1 \sim n$ can form a DFS order of this tree. Initially, no nodes are collapsed.

Every day, Liki and Sasami explore an uncollapsed node $u$. After this exploration, to guide them to discover the truth of the world, the black cat causes $u$ and all nodes in its subtree to collapse.

At the same time, after the exploration on day $i$ is completed, due to the exhaustion of their own power, node $n - i + 1$ will collapse if it has not already collapsed.

For each $i \in [1, n]$, calculate the number of exploration sequences of length exactly $i$ that Liki and Sasami can perform such that the last exploration is node 1, modulo 998244353.

Input

The first line contains a single integer $n$ ($1 \le n \le 80$), representing the number of nodes in the tree.

The next $n - 1$ lines each contain two integers $u, v$ ($1 \le u, v \le n$), representing an edge between node $u$ and node $v$.

Output

Output $n$ integers, where the $i$-th integer represents the number of exploration sequences of length $i$, modulo 998244353.

Examples

Input 1

4
1 2
2 3
2 4

Output 1

1 1 3 3 1

Note 1

For Example 1, the following 8 exploration sequences are valid: $\{1\}, \{2, 1\}, \{3, 1\}, \{4, 1\}, \{3, 2, 1\}, \{4, 2, 1\}, \{4, 3, 1\}, \{4, 3, 2, 1\}$.

Input 2

7
4 2
6 1
5 1
7 6
2 3
1 2

Output 2

1 1 6 23 48 43 17 1