Ngày xửa ngày xưa, tại một ngôi làng nhỏ dưới chân núi, có một người thợ rèn tên là Jack. Ông nổi tiếng khắp vùng vì rèn ra những vũ khí có độ bền và độ sắc bén hoàn hảo. Một ngày nọ, ông nhận được yêu cầu từ nhà vua của vương quốc chuẩn bị một số lượng lớn vũ khí cho quân đội để phòng thủ trong mùa đông sắp tới.

Jack có ~n~ loại quặng sắt hiếm, mỗi loại có trọng lượng khác nhau, và ông có thể nấu chảy tối đa ~m~ kg quặng trong lò rèn cùng một lúc. Người ta biết rằng mỗi tổ hợp quặng khác nhau sẽ tạo ra một sản phẩm khác nhau. Jack muốn tìm tất cả các cách có thể để chọn quặng đưa vào lò, sao cho tổng trọng lượng của các quặng được chọn không vượt quá ~m~ kg. Đáng chú ý, mỗi loại quặng chỉ có thể được chọn một lần.

Jack rất cẩn thận và muốn chắc chắn rằng không bỏ sót bất kỳ tổ hợp nào. Ông hy vọng rằng bạn, với tài năng toán học của mình, có thể giúp ông đếm tất cả các cách chọn quặng sao cho tổng trọng lượng nằm trong giới hạn cho phép.

Nhiệm vụ:

Hãy giúp Jack tính số cách chọn các loại quặng khác nhau sao cho tổng trọng lượng không vượt quá ~m~ kg. Vì số cách có thể rất lớn, hãy trả về kết quả theo modulo ~10^9 + 7~.

Dữ liệu vào:

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~m~ (~n, m \leq 1000~).
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, ..., a_n~ (~a_i \leq 1000~), biểu thị trọng lượng của từng loại quặng.

Dữ liệu ra:

• Một số nguyên: số cách chọn quặng sao cho tổng trọng lượng không vượt quá ~m~ kg, theo modulo ~10^9 + 7~.

Ví dụ nhập

2 16
9 7

Ví dụ xuất

4

Ghi chú

Jack có thể nấu chảy quặng như sau:

• Cách ~1: 9~
• Cách ~2: 7~
• Cách ~3: 9 \to 7~
• Cách ~4: 7 \to 9~

Giới hạn:

• Subtask ~1~ (~30%~ số điểm): ~n \leq 6~
• Subtask ~2~ (~30%~ số điểm): ~n \leq 20~
• Subtask ~3~ (~40%~ số điểm): Không có ràng buộc bổ sung.