Đếm tập con đạt tổng

Bối cảnh và bài toán

Có n thẻ số dương, mỗi thẻ dùng tối đa một lần. Hai cách được coi khác nhau nếu chọn khác tập chỉ số.

Yêu cầu

Đếm số tập con có tổng đúng S, modulo 10^9+7.

Input

Dòng 1 n S; dòng 2 các số.

Output

In số tập con modulo 10^9+7.

Ràng buộc

• 1 <= n <= 200
• 1 <= S <= 10^5
• 1 <= a_i <= 1000

Chấm điểm

Ví dụ 1

Input

4 5
1 2 3 4

Output

2

Giải thích. Ví dụ nhỏ giúp kiểm tra cách mô hình hóa trạng thái và kết quả cuối; khi tự giải, cần suy luận từ ràng buộc thay vì suy đoán từ sample.

Ví dụ 2

Input

3 7
2 4 6

Output

0

Giải thích. Hãy đối chiếu với edge case: trạng thái đầu, trạng thái không đạt được, tie hoặc biên chỉ số tùy bài.

Thông tin bài tập

Nguồn: FULLHOUSE DEV – Self-generated.