Một chiếc cầu thang có bậc, được đánh số từ đến . Bạn đang đứng ở chân cầu thang (bậc 0) và muốn đi lên đến bậc thứ . Mỗi lần, bạn có thể bước lên 1 bậc hoặc 2 bậc. Tuy nhiên, có bậc bị hỏng và bạn không được bước vào.
Hỏi có tổng cộng bao nhiêu cách khác nhau để đi hết cầu thang? Vì kết quả có thể rất lớn, hãy in ra phần dư của nó khi chia cho .
Dữ liệu:
Dòng đầu tiên chứa hai số nguyên .
Dòng thứ hai, nếu , chứa số nguyên là chỉ số của các bậc bị hỏng.
Kết quả: Một số nguyên duy nhất là số cách đi lên bậc chia dư cho .
Ví dụ:
Dữ liệu:
4 1
3
Kết quả:
2
Giải thích: Bậc bị hỏng nên không thể bước lên đó.
Các cách đi hợp lệ là:
