Sirk
n fermer Conun sirkinin inəkləri qarşıdakı çıxışlarına hazırlaşır. Bütün hadisələr 1-dən n-ə qədər nömrələnmiş zirvələri olan bir ağacda baş verir. Hərəkətin "başlanğıc vəziyyəti" k (1 ≤ k ≤ n) ədədi və inəklərin 1 .. k ağacın zirvələrinə təyin edilməsi ilə müəyyən edilir ki, heç bir iki inək eyni zirvədə olmasın.
Aktda inəklər istənilən qədər "hərəkətlər" edə bilərlər. Hərəkət zamanı bir inək öz cari zirvəsindən boş olan qonşu zirvəyə keçir. İki başlanğıc vəziyyəti ekvivalent adlanır, əgər biri digərindən müəyyən hərəkətlər ardıcıllığı ilə əldə edilə bilərsə.
Hər bir k (1 ≤ k ≤ n) üçün inəklərə başlanğıc vəziyyətlərinin ekvivalentlik siniflərinin sayını müəyyən etməyə kömək edin: yəni, ekvivalent olmayan maksimum başlanğıc vəziyyətlərinin sayını seçə bilərlər. Bu ədədlər çox böyük ola biləcəyi üçün, onları 10^9 + 7 modulu ilə çıxarın.
Giriş məlumatları
Birinci sətir n (1 ≤ n ≤ 10^5) ədədini ehtiva edir.
i-ci sətir (2 ≤ i ≤ n) a[i] və b[i] olan iki tam ədəd ehtiva edir, bu da ağacda a[i] və b[i] arasında bir kənarı göstərir.
Çıxış məlumatları
Hər bir i (1 ≤ i ≤ n) üçün k = i üçün cavabı 10^9 + 7 modulu ilə i-ci sətirdə çıxarın.
Nümunə 1
k = 1 və k = 2 üçün istənilən iki vəziyyət bir-birinə çevrilə bilər. İndi k = 3-ü nəzərdən keçirək və c[i] inək i-nin yerini göstərsin. Vəziyyət (c[1], c[2], c[3]) = (1, 2, 3) vəziyyətlərinə ekvivalentdir ( 1, 2, 5) və (1, 3, 2). Lakin (2, 1, 3) vəziyyətinə ekvivalent deyil.