问题1934--Zbc走楼梯(动态规划)

1934: Zbc走楼梯(动态规划)

[命题人 : ]
时间限制 : 1 sec  内存限制 : 128 MB

提交

题目描述

zbc的面前有n级台阶,目前他处于第0级台阶,他每一次可以选择选择爬一级台阶或是连爬两级台阶,zbc想知道他有几种到达第n级台阶的走法。出乎意料的是,n级台阶中有k级台阶被损坏了,zbc无法抵达这些被损坏的台阶。

输入

第一行给出两个正整数n,k,表示台阶的级数以及损坏的台阶数。

第二行给出k个正整数ai,表示第ai级台阶被损坏。
1 <= n <= 10^5

1 <= k,ai <= n

输出

对于每个测试样例,输出一个正整数,表示zbc到达第n级台阶的方法数。

答案对1000000007取模。

样例输入 Copy

3 1
1

样例输出 Copy

1

提示

样例输入
3 3
1 2 3
样例输出
0