Responsive image

问题 3095 --走台阶plus版

3095: 走台阶plus版

时间限制: 1 Sec  内存限制: 128 MB
提交: 0  解决: 1
[提交][状态][讨论版][命题人:]

题目描述

有n级台阶，有m级台阶不能走，分别为a1……am级台阶。
现在你要从第0级台阶出发，每次可以向上一格或两格，求走到第n级台阶的方案数mod109+7的结果。

输入描述

第一行输入n,m，接下来的m行表示不能走的台阶

1≤n≤10^5，0≤m≤n−1
1≤a1<a2<…am≤n−1

输出描述

输出方案数对109+7取余

样例输入

6 1
3

样例输出

4

提示

输入：

100 5

1

23

45

67

89

输出：

608200469

来源

22计2郝毅飞 

[提交][状态]
ACM算法攻关部