Bài toán cái túi chắc có lẽ là bài toán kinh điển khi các bạn học về quy hoạch động. Bin cũng được học về dạng này ở trường của mình. Bin khá là tự tin mình có thể làm các bài tập tương tự như vậy. Tuy nhiên hôm nay được thầy giao bài này mà bin nghĩ mãi chưa ra, các bạn hãy giúp Bin:

Cho hai số nguyên dương N và M, có M loại đồ dùng học tập có trọng lượng C1, C2, … Cm. Số lượng mỗi loại không giới hạn. Là một người có cá tính nên bạn chỉ muốn mang theo các đồ dùng học tập có trọng lượng đúng bằng N để không làm rách túi. Bạn hãy tìm xem có bao nhiêu cách mang theo đồ dùng học tập thỏa mãn.

Input

•  Dòng đầu tiên là 2 số nguyên dương N, M (N<=250, M<=50)

•  Dòng tiếp theo là C1, C2, …, Cm. (Ci <=50)

Output

•  Một số nguyên duy nhất là đáp án tìm được.

Sample

Input #1

4 3
1 2 3

Output #1

4

Problem source: NTUCoder