AT_abc129_c.[ABC129C] Typical Stairs
普及-
通过率:0%
AC君温馨提醒
该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
有 N 段的楼梯。高桥君现在在楼梯的起点(第 0 段)。高桥君每一步可以上 1 段或 2 段。
但是,第 a1,a2,a3,…,aM 段的楼梯已经损坏,踩在这些楼梯上是危险的。
在不踩到损坏楼梯的前提下,从起点到达最顶端(第 N 段)的方法有多少种?请输出方案数对 1,000,000,007 取模的结果。
输入格式
输入通过标准输入给出,格式如下:
N M a1 a2 … aM
输出格式
请输出满足条件的移动方法总数对 1,000,000,007 取模的结果。
输入输出样例
输入#1
6 1 3
输出#1
4
输入#2
10 2 4 5
输出#2
0
输入#3
100 5 1 23 45 67 89
输出#3
608200469
说明/提示
限制条件
- 1≤N≤105
- 0≤M≤N−1
- 1≤a1,a2,…,aM≤N
样例解释 1
共有以下 4 种移动方法:
- 0→1→2→4→5→6
- 0→1→2→4→6
- 0→2→4→5→6
- 0→2→4→6
样例解释 2
也有可能没有任何一种不踩到损坏楼梯的移动方法。
样例解释 3
请注意,输出的答案需要对 1,000,000,007 取模。