Ağacda hesablama#431
Sizə zirvədən ibarət bir ağac verilir. Hər bir zirvə üçün (0 \leq a[i] \leq 1) dəyəri verilib.
Bir çoxluq aşağıdakı şərtlərə cavab verirsə, gözəl adlanır:
boş deyil.
əlaqəlidir. Yəni, əgər və zirvələri -ə daxil olarsa, və arasındakı bütün zirvələr də -ə daxil olmalıdır.
daxilindəki bütün -ların cəmi -yə bərabərdir, burada verilmiş ədəddir.
Gözəl çoxluqların sayını hesablamaq tələb olunur. Bu say çox böyük ola biləcəyindən, cavabı 10^9 + 7 moduluna görə çap edin.
Birinci sətirdə testlərin sayı verilir. Hər bir test aşağıdakı sətirlərdən ibarətdir:
Birinci sətirdə iki tam ədəd (1 \leq n \leq 50000) və (1 \leq k \leq 100) verilir.
İkinci sətirdə tam ədəd a[1], a[2], \ldots, a[n] verilir.
Növbəti n-1 sətirdə hər biri və (1 \leq u, v \leq n) olan iki tam ədəd verilir, bu və zirvələri arasında bir kənar olduğunu göstərir. Verilmiş kənarların ağac əmələ gətirdiyi təmin edilir.
Hər bir test üçün cavabı ayrı sətirdə yazın.
Nümunə 1