[구름] 공연 좌석.py

# -*- coding: utf-8 -*-
# UTF-8 encoding when using korean
import sys
N = int(sys.stdin.readline())
M = int(sys.stdin.readline())
arr = [0 for _ in range(N+1)]
for _ in range(M):
	idx = int(sys.stdin.readline())
	arr[idx] = 1

# table[1][0], table[1][1] = 0은 해당 위치 사람이 자기자리, 1은 자기자리 아닌 경우
# table[2][0] = [1,2] (table[1][0] 값에서 변화 없음), table[2][1] = table[1][1]
table = [[0,0] for _ in range(N+1)]

# 첫번째 사람 = 자기 자리에만 앉을 수 있다.
table[1][0], table[1][1] = 1, 0

for person in range(2, N+1):
	# 1. 해당 사람이 자기자리에 앉는 경우 = 이전 사람이 어떻게 앉든 상관없다.
	table[person][0] = table[person-1][0] + table[person-1][1]
	# print(table[person])
	
	# 2. 해당 사람이 자기자리를 바꾸려 할 경우
	# 2-1. 이전 사람이 vip면 자리를 벗어날 수 없음
	# 2-2. 그렇지 않다면, 이전 사람이 자기자리를 지키고 있어야 자리를 바꿀 수 있다
	table[person][1] = 0 if arr[person-1] == 1 else table[person-1][0]
	
	# 해당 사람이 vip인 경우 = 자기 자리에만 앉아야 한다.
	if arr[person] == 1:
		table[person][1] = 0
	

# 마지막 사람까지의 경우의 수
print(sum(table[-1]))