ABC129 C

DP の勉強のために下記ブログの問題リストを解いてみている。
https://qiita.com/drken/items/dc53c683d6de8aeacf5a

DPだとわかっているからできるけど、自分でいきなりはまだ思いつけなさそう。
https://atcoder.jp/contests/abc129/tasks/abc129_c

import sys

line = input().split()

N = int(line[0])

M = int(line[1])

dp = [0] * (N+1)

NA = [1] * (N+1)

for i in range(M):

   NA[int(input())] = 0

for i in range(N):

   if NA[i+1] == 0 and NA[i]==0:

      print(0)

      sys.exit(0)

dp[0] = 1

dp[1] = 1

for i in range(2,N+1):

   if NA[i] == 0:

      dp[i] = dp[i-1]

   elif NA[i-1] == 0:

      dp[i] = dp[i-1]

   else:

      dp[i] = dp[i-1]*NA[i-1] + dp[i-2]*NA[i-2]

print(dp[N]%1000000007)