Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
D. Road Improvement

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputThe country has *n* cities and *n* - 1 bidirectional roads, it is possible to get from every city to any other one if you move only along the roads. The cities are numbered with integers from 1 to *n* inclusive.

All the roads are initially bad, but the government wants to improve the state of some roads. We will assume that the citizens are happy about road improvement if the path from the capital located in city *x* to any other city contains at most one bad road.

Your task is — for every possible *x* determine the number of ways of improving the quality of some roads in order to meet the citizens' condition. As those values can be rather large, you need to print each value modulo 1 000 000 007 (10^{9} + 7).

Input

The first line of the input contains a single integer *n* (2 ≤ *n* ≤ 2·10^{5}) — the number of cities in the country. Next line contains *n* - 1 positive integers *p*_{2}, *p*_{3}, *p*_{4}, ..., *p*_{n} (1 ≤ *p*_{i} ≤ *i* - 1) — the description of the roads in the country. Number *p*_{i} means that the country has a road connecting city *p*_{i} and city *i*.

Output

Print *n* integers *a*_{1}, *a*_{2}, ..., *a*_{n}, where *a*_{i} is the sought number of ways to improve the quality of the roads modulo 1 000 000 007 (10^{9} + 7), if the capital of the country is at city number *i*.

Examples

Input

3

1 1

Output

4 3 3

Input

5

1 2 3 4

Output

5 8 9 8 5

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/07/2021 18:39:17 (j2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|