Có một cầu thang với \(N\) bậc. Hiện tại, Quân đang đứng tại chân cầu thang, tức là bậc \(0\). Anh ấy có thể leo lên một hoặc hai bậc một lần.

Tuy nhiên, các bậc thang thứ \(a_1\), \(a_2\), \(a_3\), ..., \(a_M\) bị hỏng, vì vậy rất nguy hiểm nếu đặt chân lên những bậc đó.

Hãy tìm số cách để leo lên đến bậc thang cuối cùng, tức là bậc \(N\), mà không đặt chân lên các bậc thang bị hỏng. Kết quả lấy theo modulo \(1000000007\).

Ràng buộc:

• \(1 \leq N \leq 10^5\)
• \(0 \leq M \leq N-1\)
• \(1 \leq a_1 < a_2 < ... < a_M \leq N-1\)

ĐỊNH DẠNG ĐẦU VÀO

Đầu vào được cung cấp từ đầu vào chuẩn như sau:

N M
a_1 a_2 ... a_M

ĐỊNH DẠNG ĐẦU RA

In ra số cách leo lên cầu thang theo điều kiện đã cho, lấy theo modulo \(1000000007\).

Ví dụ:

Input

6 1
3

Output

4

Có bốn cách để leo lên cầu thang như sau:

• \(0 \rightarrow 1 \rightarrow 2 \rightarrow 4 \rightarrow 5 \rightarrow 6\)
• \(0 \rightarrow 1 \rightarrow 2 \rightarrow 4 \rightarrow 6\)
• \(0 \rightarrow 2 \rightarrow 4 \rightarrow 5 \rightarrow 6\)
• \(0 \rightarrow 2 \rightarrow 4 \rightarrow 6\)

Input

10 2
4 5

Output

0

Có thể không có cách nào để leo lên cầu thang mà không đặt chân lên các bậc bị hỏng.

Giải thích ví dụ mẫu:

• Ví dụ 1: Có 4 cách để leo lên cầu thang khi bậc 3 bị hỏng.

• Ví dụ 2: Không có cách nào để leo lên cầu thang khi các bậc 4 và 5 bị hỏng.

Lời giải bài tập này: Tại đây

Group giải đáp thắc mắc: Lập trình 24h

Fanpage CLB: CLB lập trình Full House- Việt Nam

Youtube: CLB Lập Trình Full House