The new semester has begun, and Bob needs to start selecting courses.

There are  courses in school, the credit for the i-th course is . Bob can select multiple times in the same course, if he select  times for the i-th course, his total credits are .

And Bob's training program has some limitations. The training program is a rooted tree of these courses, each limitation means the total credits in the subtree of  need to be at least .

Now Bob wants to know the number of ways to select courses satisfy the limitations of training program and the total credits are .

Two ways are different if and only if there exists at least one which satisfies that the select times of the i-th courses are different in these two plans.

The answer may be very large, you only need to output the answer module .

The first line has two integers .

Then there are  lines to describe the rooted tree of training program, each line has two integers  denote  is the parent node of .

Next line has   integers .

Next line has  integers .

Then there are  lines, each line has one integers  denote the total credits of the i-th query.

Output  lines, each line has one integer denote the answer of the i-th query.

3 5
1 2
1 3
1 1 2
6 2 3
10
11
12
13
1000

9
12
16
20
248004