Elearning CodePath – CTP Online Judge

LUCKYLUKE

🟢 Easy #Dynamic Programming

## Đề bài

Bờm chơi trò chơi điện tử Lucky Luke. Ở một màn chơi, Bờm phải điều khiển Lucky leo lên một cầu thang gồm $N$ bậc.

Các bậc thang được đánh số từ $1$ đến $N$ theo thứ tự từ dưới lên trên. Ban đầu, Lucky đang đứng ở bậc $1$. Lucky có thể thực hiện một trong hai cách di chuyển sau:

- đi lên đúng 1 bậc
- nhảy lên đúng 2 bậc

Tuy nhiên, có một số bậc thang đã bị hỏng, Lucky không thể đứng chân lên các bậc này. Biết rằng bậc $1$ không bao giờ bị hỏng.

Hãy tính số cách để Lucky đi từ bậc $1$ đến bậc $N$.

Vì kết quả có thể rất lớn, hãy in ra phần dư của kết quả khi chia cho $14062008$.

## Dữ liệu vào

Dữ liệu vào từ file `LUCKYLUKE.INP`.

| Dòng | Nội dung |
|---|---|
| Dòng 1 | Chứa hai số nguyên $N, K$ |
| Dòng 2 | Chứa $K$ số nguyên phân biệt theo thứ tự tăng dần, là chỉ số các bậc bị hỏng |

## Dữ liệu ra

Ghi ra file `LUCKYLUKE.OUT` một số nguyên duy nhất là số cách để Lucky đi từ bậc $1$ đến bậc $N$, lấy theo modulo $14062008$.

## Giới hạn

| Thành phần | Ràng buộc |
|---|---|
| $0 \le K < N \le 10^5$ |
| $2 \le N$ |
| Bậc $1$ không bị hỏng |
| Các chỉ số bậc hỏng nằm trong đoạn từ $2$ đến $N$ |

## Subtask

| Subtask | Điều kiện | Điểm |
|---|---|---|
| 1 | $N \le 20$ | 20\% |
| 2 | $N \le 1000$ | 30\% |
| 3 | Không có ràng buộc gì thêm | 50\% |

## Ví dụ

### Input
90000 1
49000

### Output
4108266

✅ Đã AC: 2 / 2 submissions