부분트리

트리는 사이클이 없는 연결된 무방향 그래프이다. 트리 $T$의 부분트리는 $T$의 연결된 부분 그래프이다.

부분트리의 개수는 트리의 구조에 따라 달라진다. 예를 들어 정점이 $n$개인 경로 모양 트리에는 부분트리가 $n(n+1)/2$개 있고, 별 모양 트리(중심 정점 하나에 나머지 $n-1$개 정점이 연결된 트리)에는 $2^{n-1}+n-1$개 있다.

정점을 공유하지 않는 부분트리 두 개, 세 개를 고르는 방법의 수도 트리 구조에 따라 달라진다.

구조와 관계없이, $n-1$개의 정점 비공유 부분트리를 고르는 방법은 $2n-1$가지이고, $n$개의 정점 비공유 부분트리를 고르는 방법은 1가지이다(정점 $n$개를 각각 고르는 경우).

정점이 $n$개인 트리가 주어지면, $k$를 1부터 $n$까지 바꿔 가며 정점을 공유하지 않는 부분트리 $k$개를 고르는 방법의 수를 각각 구하라.

첫 줄에 $n$($2 \le n \le 100$)이 주어진다. 다음 $n-1$개 줄에는 트리의 간선이 주어진다.

정수 $n$개를 출력한다. 각 수는 $10^9$로 나눈 나머지이다.