Thỉnh thoảng Cô giáo 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 Cô giáo 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 muốn rút.Cô giáo 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 Cô giáo 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 Cô giáo.

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}