레이팅 미적용In a distant land called Airlanvaosma-i there are \(n\) cities connected by \(n - 1\) roads.
It is possible to reach every city from any other city by passing through fewer than
36 roads.
The almighty Krešimir wants to found his own state. Krešimir’s state must have
one capital city from which the state is governed, and several (possibly none)
secondary cities that are under its administration. The size of a state is equal to
the total number of cities that belong to that state (the capital city and all secondary cities).
However, in order for the governance of the state to be efficient, Krešimir imposes the following rule:
• for every secondary city, on the path from the capital city to that secondary city there must be no
other secondary city. In other words, no secondary city may lie between the capital city and another
secondary city.
For every state size \(k\), where \(1 \le k \le n\), determine how many different states of size \(k\) the almighty
Krešimir can found. Since these numbers can be very large, output them modulo \(10^{9} + 7\).
Two choices of states are considered different if they differ in at least one chosen secondary city or in the
choice of the capital city.
The first line contains a natural number \(n\) (\(1 \le n \le 3000\)), the number of cities in the land.
In the next \(n - 1\) lines there are two natural numbers \(u\) and \(v\) (\(1 \le u\), \(v \le n\), u̸ = \(v\)), which indicate that
cities \(u\) and \(v\) are connected. It will be possible to reach every city from any other city.
In the first and only line output \(n\) numbers, the numbers described in the problem statement.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 18점 | \(1 \le n \le 15\) |
2 | 17점 | \(1 \le n \le 200\) |
3 | 26점 | \(1 \le n \le 600\) |
4 | 49점 | No additional constraints. |
4
1 2
1 3
1 44 12 6 14
1 2
2 3
1 44 12 4 0Explanation of the second sample test: There are 4 states of size 1 because there are 4 choices for
the capital city. There are 4 states of size 2 because after choosing the capital city (4 ways), we also
choose 1 secondary city (3 ways). There are 4 states of size 3 because by choosing capital cities 1 or 2 we
have 2 ways each to choose 2 additional secondary cities.