Ayvanat and Ugly Tree

All submissions for this problem are available.
Problem statement
Tidu is very pr0, but he has one weakness: Trees (maybe because trees are big and he's a smoll boi) Formally, a tree is defined as a collection of N connected nodes with N1 edges where there is only one path from a node u, to another node v. One day a friend of Tidu's, Ayvanat, had an ugly tree of N nodes. The tree was ugly because the sum of values of nodes in the tree was not equal to his favourite number: a given K. Each node in the tree had a value associated with it A[i], where A[i] is either 0 or 1. Ayvanat wants to make the tree beautiful by removing any number of nodes (and their edges) from the tree, such that the tree still remains connected. However, he immediately realises there might be too many ways to make a tree beautiful. Ayvanat asks Tidu for help since he's very pr0, but doesn't know of his weakness. Tidu turns to you for help. Your task is to count the number of ways to make the tree beautiful. Since the answer may very large, you should print it modulo 10^9 + 7.
Input
Input description.
The first line contains one integer T  the number of test cases. Then T test cases follow.
The first line of each test case contains 2 integers N and K.
The second line contains N integers a[1], a[2], ..., a[N].
Then the next N  1 line each contain pair of integers u and v (1 ≤ u, v ≤ N) denoting that there is an edge between u and v. It is guaranteed that these edges form a tree.
Output
For each test case, output a single line containing the answer, the number of ways to create a beautiful tree, modulo 10^9+7.
Constraints
Let SN be the sum of N over all test cases
1 ≤ SN ≤ 50000
1 ≤ K ≤ 100
Subtasks
Subtask 1: SN <= 25
Subtask 2: SN <= 1000
Subtask 3: Original constraints
Example
Input: 3 3 1 1 0 1 1 2 1 3 5 2 0 1 0 1 1 1 2 1 3 1 4 2 5 3 0 1 1 0 1 2 2 3 Output: 3 5 1
Author:  sinbycos 
Tags  sinbycos 
Date Added:  26102017 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 