Đếm cách đổi tiền đệ quy

Buổi 05 — Hàm & Đệ quy Mathematics
Points
35
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
recursion
Submissions
Đề bài

Cho $N$ loại tiền có mệnh giá phân biệt $C_1, C_2, \dots, C_N$ (số lượng mỗi loại không hạn chế) và một số tiền $S$. Hãy dùng đệ quy có nhớ để đếm số cách chọn các đồng tiền sao cho tổng mệnh giá bằng $S$ (không tính thứ tự các đồng tiền). Vì kết quả có thể rất lớn, hãy in ra phần dư khi chia cho $10^9 + 7$.

Dữ liệu vào

Dòng đầu chứa hai số nguyên $N$ và $S$. Dòng thứ hai chứa $N$ số nguyên dương $C_i$.

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 4\n1 2 3 4
2 3\n2 4 0
Giới hạn

$1 \le N \le 20$, $0 \le S \le 1000$, $1 \le C_i \le 1000$.

Draft saved