Bài toán: Đếm số cách tạo tổng ~ x ~ với thứ 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 (có xét thứ tự) để 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ó 3 cách sau:

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

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 (có xét thứ tự) để 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:

3

Giải thích:

• Có 3 cách khác nhau (có xét thứ tự) để tạo ra tổng ~ 9 ~ bằng các đồng xu ~ \{2, 3, 5\} ~.