Rút tiền từ ngân hàng
Thi thoảng Tichpx cũng có những giao dịch với ngân hàng, lần này là rút tiền từ ngân hàng. Ngân hàng có n loại mệnh giá tiền với số lượng các tờ tiền là vô hạn. Số tiền Tichpx muốn rút lấy ra từ ngân hàng là M, cô Giao dịch viên đã nhanh chóng đưa ra các tờ tiền với các mệnh giá tương ứng có tổng số tiền bằng M là số tiền Tichpx muốn rút. Tichpx dạy toán nên băn khoăn có còn cách nào khác lấy các tờ tiền và mệnh giá tương ứng được số tiền M nữa không. Bạn hãy trả lời băn khoăn của Tichpx nhé xem cô giao dịch viên ngân hàng có bao nhiêu cách trả các tờ tiền và mệnh giá tương ứng cho Tichpx
Input
Dòng đầu là số tiền M \((1 \le M \le 250)\) và số mệnh giá tiền n \((1 \le n \le 50)\) mà ngân hàng có
Dòng thứ hai là n mệnh giá tiền \(a_1, a_2, ..., a_n\) trong đó \((1 \le a_i \le 50)\) biết rằng số lượng tờ tiền mỗi mệnh giá là vô hạn
Output
Một số nguyên không âm là số cách mà cô giao dịch viên có thể trả tiền cho Tichpx
Ví dụ
Input
10 4
2 5 3 6
Output
5
Giải thích : Có các cách trả 10 tiền từ các mệnh giá {2, 5, 3, 6} như sau:
1 : {2, 2, 2, 2, 2}
2 : {2, 2, 3, 3}
3 : {2, 2, 6}
4 : {2, 5, 3}
5 : {5, 5}
Comments
Sao bài này mình cho n bé nhỉ