Leo cầu thang có bậc hỏng

General
Points
25
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
graph
Submissions
Đề 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$
Draft saved