Bạn có ~N~ loại xu với mệnh giá ~c_1, c_2, \ldots, c_N~ (mỗi loại có số lượng không giới hạn). Hãy đếm số cách khác nhau để tạo tổng đúng bằng ~S~.

Hai cách được coi là giống nhau nếu số xu của mỗi loại được dùng bằng nhau.

Kết quả lấy modulo ~10^9 + 7~.

Input

• Dòng đầu gồm hai số nguyên ~N~ và ~S~ (~1 \le N \le 50~, ~1 \le S \le 10000~).
• Dòng thứ hai gồm ~N~ số nguyên dương phân biệt ~c_1, c_2, \ldots, c_N~ (~1 \le c_i \le 100~).

Output

In ra số cách đổi tiền modulo ~10^9 + 7~.

Ví dụ

Input 1

3 5
1 2 3

Output 1

5

Giải thích 1

Năm cách là: ~(1,1,1,1,1)~, ~(1,1,1,2)~, ~(1,2,2)~, ~(2,3)~, ~(1,1,3)~.

Input 2

2 10
5 10

Output 2

3

Giới hạn