Leo cầu thang có bậc hỏng
Points
25
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
graph
Đề bài
Một chiếc cầu thang có $N$ bậc được đánh số từ $1$ đến $N$. Bạn đang đứng ở bậc $0$ (mặt đất) và muốn leo lên đến bậc $N$. Mỗi bước bạn có thể bước lên $1$, $2$ hoặc $3$ bậc. Tuy nhiên, có $K$ bậc thang bị hỏng không thể bước lên.
Hãy đếm số cách khác nhau để bạn đi từ bậc $0$ lên bậc $N$. Kết quả lấy phần dư khi chia cho $10^9 + 7$.
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên $N$ và $K$ ($1 \le N \le 10^5$, $0 \le K \le N$).
- Nếu $K > 0$, dòng thứ hai chứa $K$ số nguyên phân biệt là chỉ số các bậc bị hỏng (từ $1$ đến $N$).
Dữ liệu ra
Một số nguyên duy nhất là số cách leo lên bậc $N$ modulo $10^9 + 7$.
Ví dụ
| Input | Output |
|---|---|
5 1<br>3 |
5 |
Giới hạn
- $1 \le N \le 10^5$
- $0 \le K \le N$
Community Discussion