Ở thành phố Trê, bạn là hướng dẫn viên du lịch. Thành phố của bạn nổi tiếng với ~n~ điểm du lịch và mọi địa điểm đều đi đến các địa điểm khác bằng các con đường trong thành phố. Điều đặc biệt là chỉ có đúng ~n - 1~ con đường dùng để nối các địa điểm lại với nhau. Để đi vào một địa điểm du lịch, đoàn của bạn phải đang đứng ở địa điểm mà địa điểm đi tới phải được nối với điểm du lịch hiện tại.

Nhiệm vụ của bạn là soạn ra các hành trình cho các đoàn du khách tới thành phố của bạn. Mọi địa điểm được đánh số từ ~1~ tới ~n~. Để đơn giản hóa công việc, bạn quyết định diễn đạt nó bằng một dãy số là thứ tự thăm lần đầu tiên của các địa điểm du lịch. Có nghĩa là trên dãy số, địa điểm ~X~ nằm trước địa điểm ~Y~ trên dãy số khi địa điểm ~X~ được ghé thăm lần đầu tiên trước khi địa điểm ~Y~ được ghé thăm lần đầu tiên. Hành trình của bạn sẽ bắt đầu từ một địa điểm và kết thúc khi tất cả mọi địa điểm đã được ghé thăm.

Với bản đồ của thành phố Trê trong tay, bạn quyết định tính xem có bao nhiêu hành trình khác nhau bạn có thể soạn ra khi bắt đầu từ địa điểm ~i~ trong thành phố. Hai hành trình được xem là khác nhau khi hai dãy số tượng trưng cho hành trình là khác nhau.

Input

Dòng đầu tiên gồm một số nguyên dương ~n~ (~1 \le n \le 10^6~) là số lượng điểm du lịch.

~n - 1~ dòng tiếp theo chứa hai số nguyên dương ~a~ và ~b~ (~1 \le a, b \le n~) cho biết có con đường nối địa điểm ~a~ với địa điểm ~b~.

Output

Kết quả được in theo modulo ~10^9 + 7~ trên ~n~ dòng, dòng thứ ~i~ là số lượng hành trình khác nhau khi bắt đầu từ thành phố ~i~.

Scoring

Sample Input 1

5
1 2
2 3
3 4
1 5

Sample Output 1

4
6
4
1
1

Sample Input 2

6
3 6
1 3
4 2
1 4
4 5

Sample Output 2

20
4
10
20
4
2

Notes

Giải thích bộ test đầu tiên:

• Với gốc là ~1~, ta được các hành trình tương ứng là ~(1, 2, 3, 4, 5)~, ~(1, 2, 3, 5, 4)~, ~(1, 2, 5, 3, 4)~, ~(1, 5, 2, 3, 4)~.

• Với gốc là ~2~, ta được các hành trình tương ứng là ~(2, 1, 3, 4, 5)~, ~(2, 1, 3, 5, 4)~, ~(2, 1, 5, 3, 4)~, ~(2, 3, 1, 4, 5)~, ~(2, 3, 1, 5, 4)~, ~(2, 3, 4, 1, 5)~.

• ~\dots~