Nhân dịp Giỗ tổ Hùng Vương để người dân tưởng nhớ công lao các vị vua Hùng, đồng thời
nhắc nhở thế hệ trẻ những bài học về lòng yêu nước và tinh thần tự lập. Ngoài phần lễ thì ban
tổ chức còn thêm phần hội để ngày lễ được khắc sâu hơn. Có rất nhiều chương trình vui chơi
được tổ chức, một trong những trò chơi thu hút được nhiều người tham gia đó là trò chơi nhảy
lò cò, cụ thể: Người chơi cần vượt qua một đoạn đường dài N mét, có K cách nhảy với độ dài
bước nhảy tương ứng là b1 mét, b2 mét, ..., bk mét. Một cách di chuyển đúng là dãy các bước
nhảy có tổng đúng bằng N.
Yêu cầu: Cho số tự nhiên N, K và dãy b1, b2, ..., bk, gọi Q là số cách di chuyển đúng khác
nhau để người chơi đến được đoạn đường dài N mét. Tính Q.
Dữ liệu vào: File văn bản LOCO.INP gồm:
- Dòng đầu ghi N và K (hai số cách nhau một dấu cách);
- Dòng thứ hai ghi K số b1, b2, ..., bk (các số cách nhau một dấu cách và 1bi<N với i=1,2,
..., k).
Dữ liệu ra: Ghi ra file văn bản LOCO.OUT một số nguyên Q cần tìm.