Công nghiệp hóa

Bản đồ của vương quốc X gồm ~n~ thành phố đánh số từ ~0~ tới ~n - 1~ và ~n - 1~ con đường hai chiều nối giữa các thành phố. Hệ thống giao thông đảm bảo từ một thành phố bất kỳ có thể đi đến mọi thành phố khác bằng các con đường đã cho. Thành phố ~0~ là kinh đô của vương quốc.

Đức vua của vương quốc X lên kế hoạch hiện đại hóa một số thành phố. Để hiện đại hóa thành phố thứ ~i~, cần phải chi một khoản tiền là ~a_i~ từ ngân sách.

Hiện tại, đức vua đang có trong tay ~q~ bản kế hoạch, mỗi bản kế hoạch được cho bởi hai số nguyên ~u, k~ cho biết đức vua muốn hiện đại hóa một số thành phố thỏa mãn các điều kiện:

• Nếu ~S~ là tập các thành phố được hiện đại hóa thì các thành phố trong ~S~ phải liên thông, tức là có thể đi từ một thành phố thuộc ~S~ tới mọi thành phố khác thuộc ~S~ bằng các con đường có sẵn mà không cần đi qua bất kỳ thành phố nào không thuộc ~S~.
• Thành phố ~u~ phải thuộc ~S~ và là thành phố "gần" kinh đô nhất trong số tất cả các thành phố thuộc ~S~ nếu đi theo các con đường của vương quốc.
• Tổng kinh phí hiện đại hóa các thành phố thuộc ~S~ không được vượt quá ~k~.

Nhà vua đưa cho nhà kiến trúc sư các bản kế hoạch. Với mỗi bản kế hoạch, nhà kiến trúc sư băn khoăn liệu có bao nhiêu phương án chọn tập thành phố ~S~ thỏa mãn yêu cầu của bản kế hoạch. Bạn hãy giúp nhà kiến trúc sư trả lời câu hỏi này nhé.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên dương ~n, q~ ~(n \le 4000; q \le 10^5)~.
• ~n - 1~ dòng tiếp theo, mỗi dòng chứa số hiệu hai thành phố là hai đầu của một con đường.
• Dòng tiếp theo chứa ~n~ số nguyên ~a_0, a_1, \ldots, a_{n-1}~ ~(0 \le a_i \le 4000, \forall i)~.
• ~q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u, k~ ứng với một bản kế hoạch ~(0 \le u < n; a_u \le k \le 4000)~.

Kết quả

Ứng với mỗi bản kế hoạch, đưa ra số phương án lựa chọn tập thành phố ~S~. Vì kết quả có thể rất lớn, chỉ cần đưa ra số dư của kết quả khi chia cho ~10^9 + 7~.

Ví dụ

Dữ liệu vào

5 3
1 2
0 2
2 3
0 4
1 2 0 1 1
0 5
0 3
2 2

Kết quả

10
7
3

Ràng buộc

• Subtask 1 (~20\%~ số điểm): ~n \le 15, q = 1~.
• Subtask 2 (~25\%~ số điểm): ~n \le 400, k \le 400~.
• Subtask 3 (~30\%~ số điểm): ~u~ bằng nhau với mọi truy vấn.
• Subtask 4 (~25\%~ số điểm): Không có ràng buộc bổ sung.