CSES - Coin Combinations II | Kết hợp đồng xu II

Xem PDF

Điểm: 1400 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Xét một hệ thống tiền tệ với \(n\) loại đồng xu. Mỗi đồng xu có giá trị là một số nguyên dương. Hãy tính số cách khác nhau, không kể thứ tự để tạo ra tổng tiền \(x\) từ những đồng này.

Ví dụ: nếu các đồng xu là \(\{2, 3, 5\}\) và tổng mong muốn là \(9\), có \(3\) cách:

  • \(2+2+5\)
  • \(3+3+3\)
  • \(2+2+2+3\)

Input

Định dạng đầu vào:

  • Dòng đầu tiên chứa hai số nguyên \(n\)\(x\): số lượng đồng xu và tổng số tiền mong muốn.
  • Dòng thứ hai chứa \(n\) số nguyên riêng biệt \(c_1, c_2, \ldots, c_n\): giá trị của mỗi đồng xu.

Output

  • In một số nguyên duy nhất: số lượng cách, chia lấy dư cho \(10 ^ 9 + 7\).

Constraints

  • \(1\leq n \leq 100\)
  • \(1\leq x \leq 10^6\)
  • \(1\leq c_i \leq 10^6\)

Example

Sample input

3 9  
2 3 5

Sample output

3


Bình luận