Bài toán: Đếm số cách tạo tổng ~ x ~ từ các đồng xu

Đề bài

Xét một hệ thống tiền tệ gồm ~ n ~ đồng xu. Mỗi đồng xu có giá trị nguyên dương. Nhiệm vụ của bạn là tính số cách khác nhau để tạo ra tổng ~ x ~ bằng cách sử dụng các đồng xu đã cho. Kết quả cần được lấy modulo ~ 10^9 + 7 ~.

Ví dụ: Nếu các đồng xu là ~ \{2, 3, 5\} ~ và tổng cần đạt là ~ 9 ~, có 8 cách như sau:

• ~ 2 + 2 + 5 ~
• ~ 2 + 5 + 2 ~
• ~ 5 + 2 + 2 ~
• ~ 3 + 3 + 3 ~
• ~ 2 + 2 + 2 + 3 ~
• ~ 2 + 2 + 3 + 2 ~
• ~ 2 + 3 + 2 + 2 ~
• ~ 3 + 2 + 2 + 2 ~

Input

• Dòng đầu tiên chứa hai số nguyên ~ n ~ và ~ x ~:
  • ~ n ~: số lượng đồng xu.
  • ~ x ~: tổng tiền cần tạo.
• Dòng thứ hai chứa ~ n ~ số nguyên ~ c_1, c_2, \ldots, c_n ~: giá trị của từng đồng xu.

Output

• In ra một số nguyên: số cách khác nhau để tạo ra tổng ~ x ~ (modulo ~ 10^9 + 7 ~).

Ràng buộc

• ~ 1 \leq n \leq 100 ~
• ~ 1 \leq x \leq 10^6 ~
• ~ 1 \leq c_i \leq 10^6 ~

Ví dụ

Input:

3 9
2 3 5

Output:

8

Giải thích:

• Có 8 cách khác nhau để tạo ra tổng ~ 9 ~ như đã liệt kê trong phần đề bài.