Độ khó: Dễ (1/4 điểm)

📖 Bài giải chi tiết: 👉 Bấm vào đây để xem lời giải cụ thể của bài này trên blog

⚠️ Lưu ý: hãy đảm bảo em đã thật sự cố gắng tự làm bài trước, rồi mới bấm vào xem bài giải nhé!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Hôm nay Bờm đến thăm nhà A Phủ, A Phủ ở nhà sàn, để lên nhà A Phủ phải đi bằng cầu thang. Cầu thang nhà A Phủ có ~N~ bậc, trong đó có ~K~ bậc đã bị mục nên không thể bước lên được (nhà A Phủ rất nghèo, từ ngày cấm trồng cây anh túc thì nhà A Phủ sống rất khó khăn). Chú ý: Bậc thứ ~N~ là sàn nhà A Phủ, bậc này không bị hỏng. Do đi đường mệt nên Bờm chỉ còn sức để có thể bước mỗi lần một hoặc tối đa hai bậc thang mà thôi. Vừa định bước lên cầu thang thì Bờm chợt nảy ra một câu hỏi: Có bao nhiêu cách bước từ sân lên nhà A Phủ? Các em hãy tính giúp Bờm nhé.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên dương ~N~ và ~K~ cách nhau bởi một dấu cách;
• Dòng thứ hai chứa ~K~ số nguyên dương ~b_1, b_2, \ldots, b_K~ là chỉ số các bậc thang bị hỏng, mỗi số cách nhau bởi một dấu cách.

Kết quả

• Một số nguyên duy nhất là số cách bước lên nhà A Phủ (do số cách có thể rất lớn nên ta chỉ lấy phần dư khi chia cho 1000000007).

Giới hạn

• ~1 \le N \le 10^5;\ 0 \le K \le N;\ 1 \le b_i \lt N~.

Sample Input 1

5 1
2

Sample Output 1

2

Giải thích

Bờm có thể bước như sau: ~1 \to 3 \to 4 \to 5~ hoặc ~1 \to 3 \to 5~, do đó có ~2~ cách.

Nguồn: LuyenCode.