В стране есть n городов и n - 1 двусторонняя дорога, причем из каждого города можно добраться до любого другого города, двигаясь только по дорогам. Города пронумерованы целыми числами от 1 до n включительно.
Все дороги изначально плохие, однако правительство хочет улучшить состояние некоторых дорог. Будем считать, что граждане довольны улучшением дорог, если на пути от столицы, расположенной в городе x, до любого города не более одной плохой дороги на пути.
Ваша задача — для каждого возможного x определить количество способов улучшить качество некоторых дорог так, чтобы удовлетворить требованиям граждан. Поскольку искомые значения могут быть очень большими, нужно подсчитать остаток от деления каждого количества на 1 000 000 007 (109 + 7).
Выходные данные
Выведите n целых чисел a1, a2, ..., an, где ai, где ai — искомое количество способов улучшить качество дорог по модулю 1 000 000 007 (109 + 7), если столица страны находится в городе с номером i.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1 1
|
4 3 3
|
|
2
|
5
1 2 3 4
|
5 8 9 8 5
|