Đếm số cách đổi tiền

General
Points
35
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
graph
Submissions
Đề bài

Cho $N$ mệnh giá tiền phân biệt $C_1, C_2, \dots, C_N$ với số lượng không giới hạn mỗi loại. Hãy đếm số cách khác nhau để tạo thành tổng tiền $S$ (hai cách được coi là giống nhau nếu số lượng tờ tiền mỗi mệnh giá là như nhau, không phân biệt thứ tự).

Kết quả lấy phần dư khi chia cho $10^9 + 7$.

Dữ liệu vào
  • Dòng đầu chứa hai số nguyên $N, S$ ($1 \le N \le 100$, $0 \le S \le 10^4$).
  • Dòng thứ hai chứa $N$ số nguyên dương phân biệt $C_1, C_2, \dots, C_N$ ($1 \le C_i \le 10^4$).
Dữ liệu ra

Một số nguyên duy nhất là số cách đổi tiền modulo $10^9 + 7$.

Ví dụ
Input Output
3 5<br>1 2 5 4
Giới hạn
  • $1 \le N \le 100$
  • $0 \le S \le 10^4$
Draft saved