서커스

Farmer John의 서커스에는 소 $N$마리가 있으며($1 \leq N \leq 10^5$), 각 소는 다가오는 공연을 준비하고 있다. 공연은 정점에 $1, \ldots, N$번 번호가 붙은 트리 위에서 진행된다. 공연의 시작 상태는 수 $1 \leq K \leq N$과 소 $1, \ldots, K$를 트리의 정점에 배치한 방식으로 정해지며, 두 소가 같은 정점에 있을 수는 없다.

공연에서 소들은 원하는 만큼 이동할 수 있다. 한 번의 이동에서 소 한 마리가 현재 정점에서 인접한 빈 정점으로 옮겨 간다. 두 시작 상태는 한쪽에서 다른 쪽으로 일련의 이동을 거쳐 도달할 수 있으면 동치이다.

각 $1 \leq K \leq N$에 대해 시작 상태의 동치류 개수를 구하라. 즉, 소들이 서로 동치가 아닌 시작 상태를 최대한 많이 고를 때 그 개수를 구하라. 값이 매우 클 수 있으므로 $10^9 + 7$로 나눈 나머지를 출력한다.

첫 줄에 $N$이 주어진다. $2 \leq i \leq N$인 각 줄에는 트리에서 정점 $a_i$와 $b_i$를 잇는 간선을 나타내는 정수 $a_i$와 $b_i$가 주어진다.

$1 \leq i \leq N$에 대해 출력의 $i$번째 줄에는 $K = i$일 때의 답을 $10^9 + 7$로 나눈 나머지를 출력한다.