Farmer John의 서커스에 있는 $N$마리의 소($1 \leq N \leq 10^5$)가 다가오는 공연을 준비하고 있다. 모든 공연은 정점에 $1\ldots N$의 번호가 붙은 트리 위에서 이루어진다. 공연의 "시작 상태"는 수 $1 \leq K \leq N$과 소 $1\dots K$를 트리의 정점에 배치하는 방법으로 정의된다. 이때 두 소가 같은 정점에 있을 수 없다.

공연 중에 소들은 횟수에 제한 없이 "이동"할 수 있다. 한 번의 이동에서는 소 한 마리가 현재 정점에서 비어 있는 인접 정점으로 이동한다. 어떤 이동들의 연속을 통해 한 시작 상태에서 다른 시작 상태에 도달할 수 있으면 두 시작 상태가 동치라고 한다.

각 $1 \leq K \leq N$에 대해 시작 상태의 동치류 개수를 구하는 것을 도와주어라. 이는 서로 동치인 두 상태가 없도록 선택할 수 있는 시작 상태의 최대 개수이다. 이 수는 매우 클 수 있으므로 $10^9 + 7$로 나눈 나머지를 출력하여라.

입력

$1$번째 줄에는 $N$이 주어진다.

$2\le i\le N$인 각 $i$번째 줄에는 트리에서 $a_i$와 $b_i$ 사이의 간선을 나타내는 두 정수 $a_i$와 $b_i$가 주어진다.

출력

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

예제

입력 1

5
1 2
2 3
3 4
3 5

출력 1

1
1
3
24
120

참고

$K=1$과 $K=2,$일 때에는 임의의 두 상태를 서로 변환할 수 있다.

이제 $K=3$인 경우를 생각하고, $c_i$를 소 $i$의 위치라고 하자. 상태 $(c_1,c_2,c_3)=(1,2,3)$은 상태 $(1,2,5)$ 및 $(1,3,2).$와 동치이다. 하지만 상태 $(2,1,3).$과는 동치가 아니다.

입력 2

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

출력 2

1
1
1
6
30
180
5040
40320

서브태스크

• 테스트 케이스 3-4는 $N\le 8.$을 만족한다.
• 테스트 케이스 5-7은 $N\le 16.$을 만족한다.
• 테스트 케이스 8-10은 $N\le 100$을 만족하고, 트리는 "별" 형태이다. 차수가 2보다 큰 정점은 최대 하나이다.
• 테스트 케이스 11-15는 $N\le 100$을 만족한다.
• 테스트 케이스 16-20에는 추가 제한이 없다.

문제 출제: Dhruv Rohatgi