Bạn có các loại tiền mệnh giá C[1], C[2], ..., C[N]. Hãy đếm xem có bao nhiêu cách để tạo ra số tiền S từ các loại tiền đó. Giả sử số lượng mỗi loại tiền là vô hạn.

Dữ liệu vào:

Dòng 1: N và S.

Dòng 2: Các mệnh giá tiền.

Dữ liệu ra:

Số cách đổi (chia dư cho 10^9 + 7).

Ràng buộc:

1 <= N <= 100

1 <= S <= 1000

Ví dụ:

Input:

3 5 
1 2 5

Output:

4

Giải thích: (1+1+1+1+1), (1+1+1+2), (1+2+2), (5).