Codeforces Round 302 (Div. 1) |
---|
Закончено |
В стране есть 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
Название |
---|