레이팅 미적용Your local jungle is being taken over by monkeys! Trees are quickly being colonized by them! As a Brave Ape Pictures Collector, this is your chance of taking sooo many pictures of primates that for sure will amaze your colleagues.
In particular, each day, one new monkey discovers your favourite tree containing \(n\) branches. From your long experience observing primates, you know two things. First, each branch of the tree only has room for a single monkey. Second, monkeys are very social animals and always stick together in groups, that is, the branches they occupy form a single connected component.
This particular invasive species of monkeys happens to be new to you and you have not yet learned to distinguish them from each other. Still you wonder: how many different pictures of the monkey colony could you take on each day, until the tree is full of monkeys?
As an example, consider the first sample case, visualized in Figure . On the third day, there are four different pictures you can take of the monkey colony.
Monkey image from freevector.com
Given the exact structure of your favourite tree, determine for each day from \(1\) to \(n\) the number of different sets of branches the monkeys could occupy on that day, modulo \(10^9+7\).
The input consists of:
- One line with an integer \(n\) (\(1\leq n\leq 1000\)), the number of branches in the tree.
- \(n-1\) lines, the \(i\)th of which ((1\leq i\leq n-1)) contains an integer \(p_i\) (\(0\leq p_i
The branches are numbered from \(0\) to \(n-1\), inclusive. Branch \(0\) is connected to the roots of the tree and can also host a single monkey.
Output \(n\) integers. The \(k\)th integer should be the number of connected subtrees that consist of exactly \(k\) branches, modulo \(10^9+7\).
5
0
0
1
1
5
4
4
3
1
3
0
1
3
2
1