避开禁踩台阶

难度：T2

【知识点：一维动态规划】

前置知识：数组、循环、状态与转移。

题目描述

从第 $0$ 级地面出发，每次向上走 $1$ 级或 $2$ 级，恰好走到第 $n$ 级。部分台阶禁止落脚，可以一步跨过但不能落在其上。地面保证可站。求不同合法走法数，步骤顺序不同算不同走法。目标台阶可能禁踩，此时没有合法走法；$n=0$ 时空走法算一种。

输入格式

第一行两个整数 $n,m$。若 $m>0$，第二行给出 $m$ 个互不相同的禁踩级数；若 $m=0$，没有第二行。

输出格式

一行一个整数，表示走法数量，不取模。没有走法则输出 0。

样例输入

3 1
2

样例输出

1

样例解释

唯一合法路线为 $0\to1\to3$，不落在第 $2$ 级。

数据范围

$0\le n\le40$，$0\le m\le n$，禁踩级数在 $1$ 到 $n$ 之间。