Ağac
Verilmiş bir ağac var. Ağacın hər bir zirvəsi üçün həmin zirvəyə yerləşdirilə biləcək elementlər dəsti mövcuddur. Hər bir elementin müəyyən bir tam ədəd olan çəkisi var. Ağacın hər bir kənarı üçün zirvələr arasında bir münasibət müəyyən edilib, yəni iki zirvədən birində daha az çəkiyə malik elementin yerləşdirilməsi tələb olunur. Bütün kənarlar üçün bu münasibətlərin təmin edilməsi şərti ilə zirvələrdə elementlərin yerləşdirilməsinin müxtəlif yollarının sayını tapmaq lazımdır. Bir zirvənin dəstindəki müxtəlif elementlər eyni çəkiyə malik ola bilərlər.
Giriş məlumatları
Birinci sətirdə ağacda zirvələrin sayı n (1 ≤ n ≤ 1000) verilir. Sonra n sətir gəlir, burada i-ci sətir i zirvəsində icazə verilən elementlərin siyahısını göstərir. Hər sətir tam ədəd k (1 ≤ k ≤ 1000) - elementlərin sayı ilə başlayır. Ardınca k tam ədəd w[j] (1 ≤ w[j] ≤ 10^9) - elementlərin çəkiləri verilir.
Daha sonra giriş məlumatları n – 1 sətir ehtiva edir, hər birində iki müxtəlif tam ədəd a, b (1 ≤ a, b ≤ n) verilir. Bu, ağacda a və b zirvələri arasında kənar olduğunu və a zirvəsində b zirvəsindən daha az çəkiyə malik elementin yerləşdirilməli olduğunu bildirir.
Çıxış məlumatları
Modul 1000000007 ilə yolların sayını çıxış edin.