D. Улучшение дорог
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В стране есть n городов и n - 1 двусторонняя дорога, причем из каждого города можно добраться до любого другого города, двигаясь только по дорогам. Города пронумерованы целыми числами от 1 до n включительно.

Все дороги изначально плохие, однако правительство хочет улучшить состояние некоторых дорог. Будем считать, что граждане довольны улучшением дорог, если на пути от столицы, расположенной в городе x, до любого города не более одной плохой дороги на пути.

Ваша задача — для каждого возможного x определить количество способов улучшить качество некоторых дорог так, чтобы удовлетворить требованиям граждан. Поскольку искомые значения могут быть очень большими, нужно подсчитать остаток от деления каждого количества на 1 000 000 007 (109 + 7).

Входные данные

В первой строке входных данных записано одно целое число n (2 ≤ n ≤ 2·105) — количество городов в стране. В следующей строке задано n - 1 целое положительное число p2, p3, p4, ..., pn (1 ≤ pi ≤ i - 1) — описание дорог страны. Число pi означает, что в стране имеется дорога, соединяющая город pi и город i.

Выходные данные

Выведите n целых чисел a1, a2, ..., an, где ai, где ai — искомое количество способов улучшить качество дорог по модулю 1 000 000 007 (109 + 7), если столица страны находится в городе с номером i.

Примеры
Входные данные
3
1 1
Выходные данные
4 3 3
Входные данные
5
1 2 3 4
Выходные данные
5 8 9 8 5