Đếm Tập Con Có Tổng Bằng S

Cho $N$ số nguyên dương $a_1,a_2,\dots ,a_N$ và một số nguyên $S$. Đếm số tập con của dãy $a$ có tổng bằng $S$ (mỗi phần tử chỉ được chọn tối đa một lần; hai phần tử khác vị trí được coi là phân biệt ngay cả khi chúng có cùng giá trị).

Vì đáp án có thể rất lớn, hãy in ra phần dư khi chia cho ${10}^9+7$.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên $N$ và $S$.
• Dòng thứ hai chứa $N$ số nguyên $a_1,a_2,\dots ,a_N$.

Dữ liệu ra

In ra một số nguyên duy nhất: số tập con có tổng bằng $S$, lấy phần dư cho ${10}^9+7$.

Ràng buộc

• $1\le N\le 500$
• $1\le S\le {10}^4$
• $1\le a_i\le S$

Ví dụ

Ghi chú

Hai phần tử cùng giá trị nhưng khác vị trí được coi là phân biệt. Ví dụ với $a=[1,1]$, $S=1$, có $2$ tập con (chọn phần tử thứ nhất hoặc phần tử thứ hai).