Nguồn ảnh: govi.vn

Lì xì (mừng tuổi) là một phong tục quen thuộc mỗi dịp Tết: phong bao đỏ tượng trưng cho lời chúc may mắn, sức khỏe và bình an đầu năm. Để chuẩn bị "đúng bài", nhiều người thường lên danh sách đối tượng cần lì xì, dự trù tổng tiền, rồi chia nhỏ thành các mệnh giá phù hợp. Việc đổi tiền cũng cần cẩn thận để tránh rủi ro không đáng có.

Năm nay, bạn quyết định chuẩn bị lì xì theo một "lộ trình" rõ ràng gồm nhiều công đoạn (ví dụ: rút tiền, đổi mệnh giá, chuẩn bị phong bao, ghi lời chúc...). Mỗi công đoạn được gán một giá trị ~W_i~ (có thể hiểu là chi phí, thời gian, hoặc điểm công việc đã chuẩn hóa). Bạn sẽ sắp xếp thứ tự thực hiện các công đoạn theo một đồ thị có hướng, sao cho tồn tại một lộ trình từ bước ~1~ đến bước ~n~ với tổng giá trị đúng bằng ~S~.

Cho một đồ thị có hướng ban đầu chỉ có ~n~ đỉnh đánh số từ ~1~ đến ~n~. Bạn tạo các cung theo quy tắc sau:

• Với mỗi đỉnh ~i < n~, bạn chọn đúng một đỉnh ~j~ sao cho ~i < j \le n~, rồi tạo cung ~(i, j)~.

Cho trước các số ~W_1, W_2, \dots, W_n~.

Trọng số của một đường đi đi qua các đỉnh ~u_1, u_2, \dots, u_k~ (với ~u_1 = 1~, ~u_k = n~) được định nghĩa là:

$$W_{u_1} + W_{u_2} + \dots + W_{u_k}$$

Yêu cầu: hãy đếm số cách tạo cung sao cho tồn tại một đường đi từ ~1~ đến ~n~ có trọng số đúng bằng ~S~. Vì đáp án có thể rất lớn, hãy in ra theo modulo ~10^9 + 9~.

Input

• Dòng đầu tiên chứa số nguyên dương ~\tau~ là số bộ dữ liệu.

• Với mỗi bộ dữ liệu:

  • Dòng đầu chứa hai số nguyên ~n~ và ~S~ ~(1 \le n \le 4 \times 10^3,\ 0 \le S \le 5 \times 10^3)~.
  • Dòng tiếp theo chứa ~n~ số nguyên ~W_1, W_2, \dots, W_n~ ~(0 \le W_i \le 10^3)~.
• Dữ liệu đảm bảo ~\sum n + \sum S \le 5 \times 10^3~.

Output

• Với mỗi bộ dữ liệu, in ra số cách tạo cung thỏa mãn yêu cầu, modulo ~10^9 + 9~.

Scoring

Example input 1

1
4 4
1 2 2 1

Example output 1

3