数え上げ問題

C - Typical Stairs

O(N)

import sys
import math
import heapq
import itertools
from collections import deque
from functools import reduce

# main
def main():
    MOD  = 10**9+7
    N, M = list(map(int, input().split()))
    ok = [False] * (N+1)
    dp = [0] * (N+1)
    dp[0] = 1
    for _ in range(M):
        a = int(input())
        ok[a] = True

    for i in range(1, N+1):
        if ok[i]:
            continue
        if i == 1:
            dp[i] = dp[i-1]
        else:
            dp[i] = (dp[i-1] + dp[i-2]) % MOD

    print(dp[N])


# エントリポイント
if __name__ == '__main__':
    main()