Ağacda hesablama
Ağac n zirvədən ibarətdir və hər bir zirvə i üçün a[i] (0 ≤ a[i] ≤ 1) dəyəri təyin olunub.
Bir çoxluq S-i gözəl adlandırırıq, əgər aşağıdakı şərtlər ödənilirsə:
S boş deyil.
S əlaqəlidir. Yəni, əgər u və v zirvələri S-ə daxildirsə, onda u və v arasında olan bütün zirvələr də S-ə daxildir.
Bütün
a[u]-ların cəmi (u S-ə daxildir) k-yə bərabərdir, burada k verilmiş bir ədəddir.
Sizdən gözəl çoxluqların sayını hesablamaq tələb olunur. Bu say böyük ola biləcəyi üçün cavabı 10^9 + 7 modulu ilə verməlisiniz.
Giriş məlumatları
Birinci sətir testlərin sayını t göstərir. Hər bir test aşağıdakı sətirlərdən ibarətdir:
Birinci sətir iki tam ədəd n (1 ≤ n ≤ 50000) və k (1 ≤ k ≤ 100) ehtiva edir.
İkinci sətir n tam ədəd
a[1],a[2], ...,a[n]ehtiva edir.Növbəti n - 1 sətirin hər biri u və v (1 ≤ u, v ≤ n) ədədlər cütünü ehtiva edir, bu da u və v zirvələri arasında bir kənarın olduğunu göstərir. Verilmiş kənarların ağac əmələ gətirdiyi təmin edilir.
Çıxış məlumatları
Hər bir test üçün cavabı ayrı sətirdə verin.