Một quốc gia có \(n\) thành phố và \(n-1\) con đường hai chiều, sao cho có thể di chuyển từ bất kỳ thành phố nào đến bất kỳ thành phố nào khác chỉ bằng cách đi dọc theo các con đường. Các thành phố được đánh số từ \(1\) đến \(n\).

Ban đầu tất cả các đường đều ở trạng thái xấu, nhưng chính phủ muốn nâng cấp (cải thiện) một số con đường. Ta cho rằng người dân sẽ hài lòng nếu đường đi từ thủ đô nằm ở thành phố \(x\) đến bất kỳ thành phố nào khác chứa nhiều nhất một đường xấu.

Nhiệm vụ của bạn là với mỗi \(x\) (từ \(1\) đến \(n\)) tính số cách để lựa chọn một tập các con đường cần cải thiện sao cho thỏa mãn điều kiện trên. Vì kết quả có thể rất lớn, hãy in mỗi giá trị theo modulo \(10^9 + 7\).

Dữ liệu vào

• Dòng đầu tiên chứa một số nguyên \(n\) (\(2 \le n \le 2\cdot10^5\)) — số lượng thành phố.
• Dòng thứ hai chứa \(n-1\) số nguyên dương \(p_2, p_3, \dots, p_n\) (\(1 \le p_i \le i-1\)). Số \(p_i\) cho biết có một con đường nối giữa thành phố \(p_i\) và thành phố \(i\).

Dữ liệu ra

• In ra \(n\) số nguyên \(a_1, a_2, \dots, a_n\), trong đó \(a_i\) là số cách cải thiện các con đường (theo modulo \(10^9+7\)) nếu thủ đô được đặt tại thành phố \(i\).

Input 1

3
1 1

Output 1

4 3 3

Input 2

5
1 2 3 4

Output 2

5 8 9 8 5