Problem:
 Score : 300 points    Problem Statement There is a staircase with N steps. Takahashi is now standing at the foot of the stairs, that is, on the 0 -th step.
He can climb up one or two steps at a time.  However, the treads of the a_1 -th, a_2 -th, a_3 -th, \ldots , a_M -th steps are broken, so it is dangerous to set foot on those steps.  How many are there to climb up to the top step, that is, the N -th step, without setting foot on the broken steps?
Find the count modulo 1\ 000\ 000\ 007 .      Constraints  1 \leq N \leq 10^5  0 \leq M \leq N-1  1 \leq a_1 < a_2 <  ...  < a_M \leq N-1         Input Input is given from Standard Input in the following format:  N  M  a_1  a_2  .  .  .  a_M       Output Print the number of ways to climb up the stairs under the condition, modulo 1\ 000\ 000\ 007 .        Sample Input 1 6 1
3      Sample Output 1 4  There are four ways to climb up the stairs, as follows:   0 \to 1 \to 2 \to 4 \to 5 \to 6  0 \to 1 \to 2 \to 4 \to 6  0 \to 2 \to 4 \to 5 \to 6  0 \to 2 \to 4 \to 6        Sample Input 2 10 2
4
5      Sample Output 2 0  There may be no way to climb up the stairs without setting foot on the broken steps.       Sample Input 3 100 5
1
23
45
67
89      Sample Output 3 608200469  Be sure to print the count modulo 1\ 000\ 000\ 007 .

Solution (Python):

N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]

dp = [1]*N
for i in range(M):
    dp[a[i]-1] = 0

for i in range(N):
    if dp[i] == 0:
        continue
    elif i == 0:
        dp[i] = 1
    elif i == 1:
        dp[i] = dp[i-1]+1
    else:
        dp[i] = dp[i-1] + dp[i-2]

ans = int(dp[N-1])%1000000007
print(ans)

Solution (Python):

N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]

dp = [1]*N
for i in range(M):
    dp[a[i]-1] = 0

for i in range(N):
    if dp[i] == 0:
        continue
    elif i == 0:
        dp[i] = 1
    elif i == 1:
        dp[i] = dp[i-1]+1
    else:
        dp[i] = dp[i-1] + dp[i-2]

ans = int(dp[N-1])%1000000007
print(ans)

Solution (Python):
n, m = [int(i) for i in input().split()]
a = []
broken = [False] * max(n+1, 3)
for _ in range(m):
    i = int(input())
    a.append(i)
    broken[i] = True

ways = [0] * 3
ways[1] = 0 if broken[1] else 1
ways[2] = 0 if broken[2] else ways[1] + 1
for i in range(3, n+1):
    if broken[i]:
        ways.append(0)
    else:
        ways.append((ways[-2]+ways[-1])%(10**9+7))

print(ways[n])

Solution (Python):
n,m=map(int,input().split())
mod=10**9+7
dp=[1]*(n+1)
for _ in range(m):
    i=int(input())
    dp[i]=0
for i in range(n+1):
    if dp[i]==0 or i < 2: continue
    else: dp[i]=(dp[i-1]+dp[i-2])%mod
print(dp[-1])

Solution (Python):
N,M=map(int,input().split())
a=[int(input()) for _ in range(M)]

a.append(N+10)
dp=[0]*(N)
j=0

for i in range(1,N+1):
    if i==1 and 1!=a[j]:
        dp[0]=1
    elif i==2:
        if 2==a[j]:
            dp[1]=0
            j+=1
        else:
            dp[1]=dp[0]+1

    elif i!=a[j]:
        dp[i-1]=dp[i-2]+dp[i-3]
    else:
        j+=1
    

print(dp[N-1]%1000000007)

Solution (Python):
N, M = map(int, input().split())
A = set([int(input()) for i in range(M)])
B = [0]*(N+1)
B[0] = 1
for i in range(1, N+1):
    B[i] = B[i-1] + B[i-2]
    if i in A:
        B[i] = 0
print(B[N]%1000000007)

Solution (Python):
n,m = map(int, input().split())
mod = 10**9+7

lst = []
for i in range(m):
    lst.append(int(input()))
lst.sort()


dp = [-1 for i in range(n+2)]
dp[0] = 1
dp[1] = 1
for i in lst:
    dp[i] = 0
for i in range(2,n+2):
    if dp[i]<0:
        dp[i] = dp[i-1] + dp[i-2]




print(dp[n]%mod)

Solution (Python):
n,m = map(int, input().split())
mod = 10**9+7


dp = [0 for i in range(n+2)]
dp[0] = 1
dp[1] = 1
for i in range(2,n+2):
    dp[i] = dp[i-1] + dp[i-2]


if m==0:
    print(dp[n]%mod)
    exit()

lst = []
for i in range(m):
    lst.append(int(input()))
lst.sort()


for i in range(len(lst)-1):
    if lst[i]+1 == lst[i+1]:
        print(0)
        exit()

lst2 = []
for i in range(len(lst)):
    if i==0:
        lst2.append(lst[0]-1)
    else:
        lst2.append(lst[i]-lst[i-1]-2)
lst2.append(n-lst[-1]-1)

ans = 1
for i in lst2:
    ans *= dp[i]
    ans %= mod



print(ans)

Solution (Python):
n,m=map(int,input().split())
a=set([int(input()) for o in range(m)])
dp=[0]*(n+1)
dp[0]=1
for i in range(1,n+1):
    dp[i]=(dp[i-1]+dp[i-2])%(10**9+7)
    if i in a:
        dp[i]=0
print(dp[n])

Solution (Python):
MOD=1000000007
N,M=map(int,input().split())
a=[]
dp=[0]*100010
for i in range(M):
    tmp=int(input())
    a.append(tmp)
    dp[tmp]=-1
dp[0]=1
for i in range(1,N+1):
    if(dp[i]==-1):
        continue
    if(dp[i-1]!=-1):
        dp[i]=(dp[i]+dp[i-1])%MOD
    if(i>1):
        if(dp[i-2]!=-1):
            dp[i]=(dp[i]+dp[i-2])%MOD
print(dp[N])

Solution (Python):
mod = 10**9 + 7
N, M = map(int, input().split())


a = [True] * (N+1)
for _ in range(M):
    a[int(input())] = False


dp = [0] * (N+1)
dp[0] = 1
for i in range(N+1):
    for j in range(1, 3):
        if (i+j) > N or a[i+j] == False:
            continue
        dp[i+j] += dp[i]
        dp[i+j] %= mod

print(dp[N])

Solution (Python):
MOD = 10**9+7
n,m = map(int,input().split())

f = [1,1]
for i in range(2, n+1):
    f.append(f[i-2]+f[i-1])

cur = 0
ans = 1
for i in range(m):
    a = int(input())
    if a==cur:
        print(0)
        break
    ans *= f[a-cur-1]
    ans %= MOD
    cur = a+1
else:
    ans *= f[n-cur]
    ans %= MOD
    print(ans)

Solution (Python):
N,M = map(int, input().split())
a = [-1]*(M+2)
a[M+1] = N+1
diff = 0
for i in range(1,M+2):
    if i != M+1: a[i] = int(input())
    diff = max(diff, a[i]-a[i-1])

inf = 10**9+7

dp = [0]*diff
dp[0] = 0
dp[1] = 1
for i in range(2,diff):
    dp[i] = dp[i-1] + dp[i-2]
    dp[i] = dp[i]%inf

cnt = 1
for i in range(1,M+2):
    da = a[i]-a[i-1]-1
    if da == 0:
        cnt = 0
        break
    else:
        cnt *= dp[da]
        cnt = cnt%inf

print(cnt%inf)

Solution (Python):



def main():
  MAX = 10**9+7
  
  n, m = map(int, input().strip().split())
  As = set([int(input()) for _ in range(m)])
  
  dp = [0] * (n + 1)
  dp[0] = 1
  dp[1] = 1 if 1 not in As else 0
  for i in sorted(list(set(range(2, n+1)) - As)):
    dp[i] = (dp[i-1] + dp[i-2]) % MAX
  print(dp[-1] % MAX)
  
if __name__=='__main__':
  main()

Solution (Python):
def main():

    N, M = map(int, input().split())
    A = [True] * (N + 1)
    for i in range(M):
        a = int(input())
        A[a] = False

    dp = [0] * (N + 1)
    dp[0] = 1

    for i in range(0, N - 1):
        if not A[i]:
            continue
        if A[i+1]:
            dp[i+1] += dp[i]
        if A[i+2]:
            dp[i + 2] += dp[i]
        dp[i] %= 1000000007

    if A[N-1]:
        dp[N] += dp[N - 1]

    print(dp[N] % 1000000007)


main()

Solution (Python):
N, M = map(int, input().split())
A = set()
for _ in range(M):
    A.add(int(input()))
p = 10 ** 9 + 7
DP = [0 for _ in range(N + 1)]
DP[0] = 1
if 1 in A:
    DP[1] = 0
else: DP[1] = 1
for i in range(2, N+1):
    if i in A:
        DP[i] = 0
    else:
        DP[i] = (DP[i-1] + DP[i-2])%p
print(DP[N])

Solution (Python):
n,m=map(int,input().split())
A={int(input()) for _ in range(m)}
mod=10**9+7

dp=[0]*(n+1)
dp[0]=1
if 1 not in A:
   dp[1]=1

for i in range(2,n+1):
   if i not in A:
      dp[i]=dp[i-1]+dp[i-2]
print(dp[-1]%mod)

Solution (Python):
n,m=map(int,input().split())
A={int(input()) for _ in range(m)}
mod=10**9+7

dp=[0]*(n+1)
dp[0]=1
if 1 not in A:
   dp[1]=1

for i in range(2,n+1):
   if i not in A:
      dp[i]=dp[i-1]+dp[i-2]
print(dp[-1]%mod)

Solution (Python):
n,m = map(int,input().split())

j = [True for i in range(n+1)]

ans = [1,1]+[0 for i in range(n-1)]
p = 10**9+7

for i in range(m):
    j[int(input())] = False
    

if j[1] == False:
    ans[1] = 0
    ans[2] = ans[0]

for i in range(2,n+1):
    
    if j[i] == True:
        ans[i] = ans[i-1] + ans[i-2]
        ans[i] %= p
    
    else:
        ans[i] = 0
        
print(ans[n]%p)

Solution (Python):
n,m=map(int,input().split())
j=[True for _ in range(n+1)]
ans=[1,1]+[0 for _ in range(n-1)]
p=10**9+7
for _ in range(m):
    j[int(input())]=False
if j[1]==False:
    ans[1]=0
    ans[2]=ans[0]
for i in range(n-1):
    if j[i+2]==True:
        ans[i+2]=ans[i+1]+ans[i]
        ans[i+2]%=p
    else:
        ans[i+2]=0
print(ans[n]%p)

Solution (Python):
N, M = map(int,input().split())
a = [int(input()) for _ in range(M)]
mod = pow(10,9) + 7

dp = [0]*(N+1)
dp[0] = 1

ok = [True]*(N+1)
for i in a:
  ok[i] = False

for i in range(N):
  for j in range(i+1,min(N+1,i+3)):
    if ok[j]:
      dp[j] += dp[i]
      dp[j] %= mod
      
print(dp[N])

Solution (Python):
n, m = map(int, input().split())
a = [int(input()) for i in range(m)]

mod = 10 ** 9 + 7
ok = [True] * (n + 1)
for i in a:
    ok[i] = False

dp = [0 for i in range(n+1)]
dp[0] = 1
for i in range(n):
    for j in range(i+1, min(n+1, i+3)):
        if ok[j]:
            dp[j] += dp[i]
            dp[j] %= mod

print(dp[n])

Solution (Python):
N, M = map(int, input().split())

flag = [0]*N
for i in range(M):
    flag[int(input())-1] = 1


    

mod = 10**9+7

dp = [0] * N

if flag[0]==0:

    dp[0] = 1
    if N>1:
        if flag[1]==0:
    
            dp[1] = 2
elif N > 1:
    if flag[1]==0:
    
        dp[1] = 1
    else:
        dp[1] = 0

loop = []
'''
for i in range(2, N):
    if i not in A:
        loop.append(i)
'''
for i in range(2, N):
    if flag[i]==0:
        dp[i] = (dp[i-2] + dp[i-1]) % mod
        

print(dp[N-1])

Solution (Python):
n, m = map(int, input().split())
a = [int(input()) for i in range(m)]

mod = 10**9+7
dp = [-1]*(n+1)
dp[0] = 1
dp[1] = 1

for i in a:
    dp[i] = 0

for i in range(2, n+1):
    if dp[i] < 0:
        dp[i] = (dp[i-1] + dp[i-2])%mod

print(dp[n])

Solution (Python):
n, m = map(int, input().split())
counts = [-1] * (n + 1)
counts[0] = 1
counts[1] = 1
for _ in range(m):
  counts[int(input())] = 0
for i in range(2, n + 1):
  if counts[i] < 0:
    counts[i] = (counts[i - 1] + counts[i - 2]) % 1000000007
print(counts[n])

Solution (Python):
n,m=map(int,input().split())
dp=[0]*(n+3)
a=[int(input()) for i in range(m)]
mod=10**9+7
for i in range(m):
    dp[a[i]]=-1

dp[0]=1
if dp[1]!=-1:
    dp[1]+=dp[0]

for i in range(n+1):
    if dp[i+2]==-1:
        continue
    if dp[i]!=-1:
        dp[i+2]+=dp[i]
    if dp[i+1]!=-1:
        dp[i+2]+=dp[i+1]
    dp[i+2]%=mod
print(dp[n]%mod)

Solution (Python):
n, m = map(int, input().split())
p = 1000000007
dp = [0] * n
c = 0
for _ in range(m):
    a = int(input())
    dp[a - 1] = -1
for i in range(1, n):
    if i <= 1:
        if dp[0] != -1 and dp[1] != -1:
            dp[0], dp[1] = 1, 2
        elif dp[0] == -1 and dp[1] != -1:
            dp[0], dp[1] = 0, 1
        elif dp[0] != -1 and dp[1] == -1:
            dp[0], dp[1] = 1, 0
        else:
            c = -1
    if i >= 2 and dp[i] != -1:
        if dp[i - 1] == -1 and dp[i - 2] != -1:
            dp[i] = dp[i - 2]
        elif dp[i - 1] != -1 and dp[i - 2] == -1:
            dp[i] = dp[i - 1]
        elif dp[i - 1] != -1 and dp[i - 2] != -1:
            dp[i] = (dp[i - 1] + dp[i - 2]) % p
        else:
            c = -1
if c == -1:
    print(0)
elif n == 1:
    print(1)
else:
    print(dp[n - 1])

Solution (Python):
CONST = 10**9 + 7
n,m = map(int,input().split())

dp = [-1 for _ in range(n+1)]
dp[0] = 1
dp[1] = 1
for _ in range(m):
  a = int(input())
  dp[a] = 0


for i in range(2,n+1):
  if dp[i] == 0:
    continue
  dp[i] = (dp[i-1] + dp[i-2]) % CONST
print(dp[n])

Solution (Python):
n,m,*a=map(int,open(0).read().split())
d=[1]*(n+1)
for i in a:
    d[i]=0
for i in range(2,n+1):
    if d[i]!=0:
        d[i]=d[i-1]+d[i-2]
print(d[-1]%(10**9+7))

Solution (Python):
n,m,*a=map(int,open(0).read().split())
dp=[-1]*(n+1)
for i in a:
    dp[i]=0
dp[0]=1 
for i in range(1,n+1):
    if dp[i]!=0:
        dp[i]=dp[i-1]+dp[i-2]*(i>1)
print(dp[-1]%(10**9+7))

Solution (Python):
n, m = map(int, input().split())

MOD = 10**9+7

dp = [0]*(n+1)
dp[0] = 1
broken = [0]*(n+1)
for i in range(m):
    broken[int(input())] = 1
    
for i in range(1, n+1):
    if broken[i] == 1:
        continue
    else:
        if i != 1:
            dp[i] = dp[i-1] + dp[i-2]
        elif i == 1:
            dp[i] = dp[i-1]

print(dp[-1]%MOD)

Solution (Python):
import sys 
sys.setrecursionlimit(50000000) 
N,M=map(int,input().split())
a=[]
for i in range(0,M):
    a.append(int(input()))
a=set(a)
if M==0:
    a=[-1]
ans=1
s=[-1]*(N+1)
s[0]=1
def dp(n):
    if n==0:
        return 1
    elif n==1:
        return 0 if 1 in a else 1
    if s[n-1]!=-1:
        c=s[n-1]
    elif n-1 in a:
        s[n-1]=0
        c=0
    else:
        c=dp(n-1)%1000000007
        s[n-1]=c
    if s[n-2]!=-1:
        b=s[n-2]
    elif n-2 in a:
        s[n-2]=0
        b=0
    else:
        b=dp(n-2)%1000000007
        s[n-2]=b
    return (c+b)%1000000007
print(dp(N)%1000000007)

Solution (Python):
const = 1000000007
n, m = [int(_) for _ in input().split()]
dp = [0]* (n+2)

for _ in range(m):
    dp[int(input())] = -1

dp[0] = 1
dp[n+1] = -1

for i in range(0, n):
    if dp[i] != -1:
        if dp[i+1] != -1:
            dp[i+1] += dp[i]
        if dp[i+2] != -1:
            dp[i+2] += dp[i]

print(dp[n]%const)

Solution (Python):
N, M = map(int, input().split())
a = set([int(input()) for i in range(M)])
 
dp = [0] * (N+1)
dp[0] = 1
for i in range(1, N+1):
    dp[i] = (dp[i-1] + dp[i-2]) % (10**9+7)
    if i in a:
        dp[i] = 0
print(dp[N])

Solution (Python):
n, m = [int(x) for x in input().split()]
a = set([int(input()) for _ in range(m)])

 
memo = [0]*(n + 1)
 
for i in range(n+1):
  if i in a:
    continue
  else:
    if i == 0 or i == 1:
      memo[i] = 1
    else:
      memo[i] = (memo[i-1] + memo[i-2])%((10**9)+7)
 
print(memo[n])

Solution (Python):
n,m = map(int,input().split())
a_lst = set(int(input()) for i in range(m))
dp = [0]*(n+1)
dp[0] = 1
x = 10**9 + 7

for i in range(1,n+1):
    if i in a_lst:
        continue
    else:
        if i==1:
            dp[i] = dp[i-1]
        elif i>1:
            dp[i] = (dp[i-2] + dp[i-1]) % x

answer = dp[-1]

print(answer)

Solution (Python):
n,m=map(int,input().split())
a=[int(input()) for _ in range(m)]

mod=10**9+7

oks = [True]*(n+1)
for i in range(m):
    oks[a[i]] = False

dp=[0]*(n+1)
dp[0]=1
for now in range(0,n):
    for nex in range(now+1,min(n,now+2)+1):
        if oks[nex]:
            dp[nex]+=dp[now]
            dp[nex]%=mod
print(dp[n])

Solution (Python):
n, m = map(int, input().split())
a = set([int(input()) for _ in range(m)])
NUM = 10 ** 9 + 7

dp = [0] * (n+1)
dp[0] = 1
if not 1 in a:
    dp[1] = 1

for i in range(2, n+1):
    if not i in a:
        dp[i] = (dp[i-2] + dp[i-1]) % NUM
    else:
        dp[i] = 0

print(dp[n])

Solution (Python):

MOD = 1000000007

def main():
    n,m = map(int,input().split())
    al = [False for _ in range(n+1)]
    for i in range(m):
        a = int(input())
        al[a] = True
    
    dp = [0 for _ in range(n+1)]
    dp[0] = 1
    dp[1] = 1 if al[1] == False else 0

    for i in range(2,n+1):
        if not al[i]:
            dp[i] = (dp[i-2] + dp[i-1]) % MOD

    print(dp[n])


if __name__ == "__main__":
    main()

Solution (Python):

MOD = 1000000007

def main():
    n,m = map(int,input().split())
    al = [False for _ in range(n+1)]
    for i in range(m):
        a = int(input())
        al[a] = True
    
    dp = [0 for _ in range(n+1)]
    dp[0] = 1
    dp[1] = 1 if al[1] == False else 0

    for i in range(2,n+1):
        if not al[i]:
            dp[i] = dp[i-2] + dp[i-1]

    print(dp[n] % MOD)


if __name__ == "__main__":
    main()

Solution (Python):
n,m=map(int,input().split())
a=[]
mod=1e9+7
oks=[True]*(n+1)
for i in range(m):
    a.append(int(input()))
    oks[a[i]]=False
dp=[0]*(n+1)
dp[0]=1
for i in range(n):
    for j in range(i+1, min(n,i+2)+1):
        if oks[j]:
            dp[j]+=dp[i]
            dp[j]%=mod

print(int(dp[n]))

Solution (Python):
[n,m] = [int(i) for i in input().split()]
a = []
for i in range(m):
    a.append(int(input()))
ok = [0] * (n+1)
for i in range(m):
    ok[a[i]] = 1
dp = [0] * (n+1)
dp[0] = 1
if n > 1:
    for i in range(1,n+1):
        if ok[i] != 1:
            if i == 1:
                dp[i] = 1
            else:
                dp[i] = (dp[i-2]+dp[i-1])%(10**9+7)
        else:
            dp[i] = 0
    print((dp[n])%(10 ** 9 + 7))
else:
    if 1 in a:
        print(0)
    else:
        print(1)

Solution (Python):
n, m = [int(x) for x in input().split()]
a = set(int(input()) for _ in range(m))

mod = 10 ** 9 + 7

dp = [0] * (n + 1)
dp[0] = 1
for i in range(1, n + 1):
    if i in a:
        continue
    if i >= 2:
        dp[i] = (dp[i - 1] + dp[i - 2]) % mod
    else:
        dp[i] = dp[i - 1]
print(dp[-1])

Solution (Python):
n,m=map(int,input().split())
a=set([int(input()) for i in range(m)])
dp=[0]*(n+1)
dp[0]=1
for i in range(1,n+1):
    dp[i]=(dp[i-1]+dp[i-2])%(10**9+7)
    if i in a:dp[i]=0
print(dp[n])

Solution (Python):
def main():
    n, m = map(int, input().split())
    num_list = [int(input()) for _ in range(m)]

    dp = [0] * (n+1)
    dp[0] = 1
    
    for num in num_list:
        dp[num] = -1

    if dp[1] != -1:
        dp[1] = 1
    else:
        dp[1] = 0

    for i in range(2,n+1):
        if dp[i] == -1:
            dp[i] = 0
            continue
        dp[i] = dp[i - 1] + dp[i - 2]

    print(dp[n]%1000000007)

if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
 

def ii(): return int(sys.stdin.readline().rstrip()) 
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) 
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]

def ss(): return sys.stdin.readline().rstrip() 
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) 
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]





INF=-float("inf")

n,m=mii()

arr=lin(m)

dp=[0]*(n+1)

for i in arr:
    dp[i]=INF

if n==1:
    print(1)
    exit()

if dp[1]!=INF:
    dp[1]=1

if dp[1]==INF and dp[2]!=INF:
    dp[2]=1

elif dp[1]==INF and dp[2]==INF:
    print(0)
    exit()
elif dp[1]!=INF and dp[2]!=INF:
    dp[2]+=dp[1]
    

for i in range(2,n+1):
    if dp[i]!=INF:
        if dp[i-1]!=INF and dp[i-2]==INF:
            dp[i]+=dp[i-1]
        elif dp[i-1]==INF and dp[i-2]!=INF:
            dp[i]+=dp[i-2]
        elif dp[i-1]!=INF and dp[i-2]!=INF:
            dp[i]+=dp[i-1]+dp[i-2]
        else:
            dp[i]=0

print(dp[-1]%mod)

Solution (Python):
n, m = map(int, input().split())
a = [False]*(n+1)
for i in range(m):
  ii = int(input())
  a[ii] = True
  
dp = [0]*(n+1)
dp[0] = 1

mod = 1000000007
for i in range(1, n+1):
  if a[i]:
    dp[i] = 0
    continue
  dp[i] = (dp[i-1] + dp[i-2]) % mod

print(dp[-1])

Solution (Python):


N, M = [int(x) for x in input().split()]
a = set(int(input()) for _ in range(M))

MOD = 10 ** 9 + 7
dp = [0] * (N + 1)
dp[0] = 1

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

ans = dp[N]
print(ans)

Solution (Python):
n, m = map(int, input().split())
broken = [0 for _ in range(n)]
for _ in range(m):
    broken[int(input())] = 1
mod = 1000000007
dp = [0 for _ in range(n+2)]
dp[n] = 1
for i in range(n)[::-1]:
    if(broken[i]):
        dp[i] = 0
        continue
    dp[i] = (dp[i+1] + dp[i+2]) % mod
print(dp[0])

Solution (Python):
n,m=map(int,input().split())
broken=[]
for i in range(m):
  broken.append(int(input()))
b=set(broken)
l=[1]
for j in range(1,n+1):
  if j in b:
    l.append(0)
  elif j==1:
    l.append(1)
  else:
    l.append(l[j-2]+l[j-1])
print(l[n]%(10**9+7))

Solution (Python):
n , m = map(int,input().split())
a = [int(input()) for _ in range(m)]

broken = set(a)
mod = 10**9 + 7

dp = [0] * (n + 1)
dp[0] = 1

for i in range(1,n +1):
    if i in broken:
        continue

    if i == 1:
        dp[1] = dp[0]
        continue

    dp[i] = dp[i-1] + dp[i-2]
    dp[i] %= mod

print(dp[n])

Solution (Python):
from functools import lru_cache
import sys
sys.setrecursionlimit(1000000)

N, M = map(int, input().split())
mod = 10**9+7

a = [1] * (N+1)
for _ in range(M):
    a[int(input())] = 0

@lru_cache()
def f(x):
    v = 0
    if x<0:
        return 0
    if x == 0:
        return 1
    if a[x-1]:
        v += f(x-1)
    if a[x-2]:
        v += f(x-2)
    v %= mod
    return v

print(f(N))

Solution (Python):
n, m = map(int, input().split())
li = [True]*(n+1)

for i in range(m):
    a = int(input())
    li[a] = False

dan = [0]*(n+1)
dan[0] = 1

for j in range(1,n+1):
    if li[j]:
        dan[j] += dan[j-1]
        if j >= 2:
            dan[j] += dan[j-2]

print(dan[n]%(10**9+7))

Solution (Python):
n,m = map(int,input().split())

p = [True for _ in range(n+1)]

p[0] = 1
p[1] = 1

for _ in range(m):
    a = int(input())
    p[a] = 0

for i in range(2,n+1):
    if p[i]:
        p[i] = p[i-1] + p[i-2]

print(p[n]%(10**9+7))

Solution (Python):
n,m = map(int,input().split())

p = [True for _ in range(n+1)]

p[0] = 1
p[1] = 1

for _ in range(m):
    a = int(input())
    p[a] = False

for i in range(2,n+1):
    if p[i] == False:
        p[i] = 0
    else:
        p[i] = p[i-1] + p[i-2]

print(p[n]%(10**9+7))

Solution (Python):
N,M=map(int,input().split())
A=[int(input()) for i in range(M)]

mod=10**9+7
dp=[0]*(N+1)
dp[0]=1

isbroken=[1]*(N+1)
for i in range(M):
    isbroken[A[i]]=0

for i in range(N):
    if i-1>=0:
        dp[i+1]=dp[i]*isbroken[i]+dp[i-1]*isbroken[i-1]
    else:
        dp[i+1]=dp[i]*isbroken[i]
    dp[i+1]%=mod

print(dp[-1])

Solution (Python):
import sys

MOD = 10 ** 9 + 7

n, m, *a = map(int, sys.stdin.read().split())
broken = set(a)

def main():
    res = [None] * (n + 1)
    res[0] = 1
    res[1] = 0 if 1 in broken else 1
    
    for i in range(2, n+1):
        if i in broken:
            res[i] = 0
        else:
            res[i] = res[i-2] + res[i-1]
            res[i] %= MOD
    
    return res[n]
    
if __name__ == '__main__':
    ans = main()
    print(ans)

Solution (Python):

n,m = map(int,input().split())
a = [int(input()) for _ in range(m)]
dp = [-1]*(n+2)
dp[0] = 0
dp[1] = 1
mod = 10**9+7
for i in a:
    dp[i+1] = 0
for i in range(n+2):
    if dp[i] == -1:
        dp[i] = (dp[i-1]+dp[i-2])

print(dp[n+1]%mod)

Solution (Python):
import os, sys, re, math, queue

def run_it():
	N,M = list(map(int,input().split(' ')))
	divider = 1000000007
	n_max = 100000
	memo = [0] * (n_max + 1)
	memo[0] = 1
	memo[1] = 1
	for i in range(2,n_max+1):
		memo[i] = (memo[i-2] + memo[i-1]) % divider
	
	cur = 0
	ret = 1
	for m in range(M+1):
		if m < M:
			a = int(input())
		else:
			a = N + 1
		
		if a == cur:
			ret = 0
			break
		ret *= memo[a-cur-1]
		ret %= divider
		cur = a + 1

	print(ret)

if sys.platform == 'ios':
	for i in range(3):
		sys.stdin = open('Ctest' + str(i) + '.txt')
		run_it()
else:
	run_it()

Solution (Python):
n,m=map(int,input().split())
A=set(int(input()) for i in range(m))
 
x=[0]*(n+1)
x[0]=1
if 1 in A:
    x[1]=0
else:
    x[1]=1
 
for j in range(2,n+1):
    if j in A:
        x[j]=0
    else:
        x[j]=(x[j-1]+x[j-2])%(10**9+7)
        
 
print(x[n])

Solution (Python):
n,m=map(int,input().split())
A=set(int(input()) for i in range(m))
dp=[0]*(n+1)
dp[0]=1
for i in range(1,n+1):
    dp[i]=(dp[i-1]+dp[i-2])%(10**9+7)
    if i in A:dp[i]=0
print(dp[n])

Solution (Python):
mod = 1000000007
n, m = map(int, input().split())
b = [0] * (n + 1)
for _ in range(m):
    b[int(input())] = 1
dp = [1] + [0] * n
for i in range(1, n + 1):
    if b[i] == 1:
        dp[i] = 0
    elif i == 1:
        dp[i] = dp[i - 1]
    else:
        dp[i] = (dp[i - 1] + dp[i - 2]) % mod
print(dp[n])

Solution (Python):
n, m = list(map(int, input().split(' ')))
aaa = [0] * (n + 3)
for i in range(m):
    aaa[int(input())] = True

dp = [1] * (n + 3)
for i in range(1, n+1):  
    if not aaa[i]:
        dp[i]  = dp[i-1]
        if i >= 2:
            dp[i] += dp[i-2]
        dp[i] = dp[i] % int(1e9 + 7)
    else:
        dp[i] = 0
print(dp[n])

Solution (Python):
n,m = map(int,input().split())
A = list()
for i in range(m):
    a = int(input())
    A.append(a)
dp = [0]*(n+1)
dp[0] = 1
if 1 in A:
  del A[0]
else:
  dp[1] = 1
for i in range(2,n+1):
    if len(A) != 0:        
        if i != A[0]:
            dp[i] = dp[i-2] + dp[i-1]
            dp[i] = dp[i]%1000000007
        else:
          del A[0]
    else:
        dp[i] = dp[i-2] + dp[i-1]
        dp[i] = dp[i]%1000000007
print(dp[-1]%1000000007)

Solution (Python):
N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]
q = 1000000007

if N == 1:
    if M == 0:
        print(1)
    elif M == 1:
        print(0)
else:
    cost = [0 for _ in range(N + 1)]
    cost[0] = 1

    cnt = 0
    A.append([0])
    for i in range(1, N + 1):
        if i == A[cnt]:
            cnt += 1
            continue
        else:
            cost[i] = cost[i - 1] + cost[i - 2]

    print(cost[-1] % q)

Solution (Python):
N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]
q = 1000000007

if N == 1:
    if M == 0:
        print(1)
    elif M == 1:
        print(0)
else:
    cost = [0 for _ in range(N + 1)]
    cost[0] = 1

    cnt = 0
    A.append([0])
    for i in range(1, N + 1):
        if i == A[cnt]:
            cnt += 1
            continue
        else:
            cost[i] = cost[i - 1] + cost[i - 2]

    print(cost[-1] % q)

Solution (Python):
N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]
q = 1000000007

if N == 1:
    if M == 0:
        print(1)
    elif M == 1:
        print(0)
else:
    cost = [0 for _ in range(N + 1)]
    cost[0] = 1

    cnt = 0
    A.append([0])
    for i in range(1, N + 1):
        if i == A[cnt]:
            cost[i] = 0
            cnt += 1
        else:
            cost[i] = (cost[i - 1] + cost[i - 2]) % q

    print(cost[-1])

Solution (Python):
n, m = map(int, input().split())
lst = [True] * (n + 1)
for _ in range(m):
    a = int(input())
    lst[a] = False
dp = [0] * (n + 1)
dp[0] = 1
div = 10 ** 9 + 7
for i in range(1, n + 1):
    if  lst[i]:
        dp[i] += dp[i - 1]
        dp[i] = dp[i] % div
        if i > 1:
            dp[i] += dp[i - 2]
            dp[i] = dp[i] % div

print(dp[n])

Solution (Python):
mod = 10**9 + 7

n, m = map(int, input().split())
fib = [1] * (n+1)
for i in range(2, n+1):
  fib[i] = (fib[i-1] + fib[i-2]) % mod
count = 1
start = 0
for _ in range(m):
  a = int(input())
  stop = a-1
  if start > stop:
    count = 0
    break
  count = count * fib[stop - start] % mod
  start = a+1
stop = n
count = count * fib[stop - start] % mod
print(count)

Solution (Python):


NM = input()
N = int(NM.split(' ')[0])
M = int(NM.split(' ')[1])

a = []
for i in range(M):
    a.append(int(input()))

a = sorted(a)
a.append(0)

dp = [0] * (N+1)
dp[0] = 1


for i in range(1,N+1):
    
    if(a[0] == i):
        dp[i] = 0
        del a[0]
        continue

    if(i>1):
        dp[i] = dp[i-1] + dp[i-2]
    else:
        dp[i] = dp[i-1]

print(dp[N]%(10**9 + 7))

Solution (Python):
n,m = map(int,input().split())
ans = [1]*(n+1)
for i in range(m):
    a = int(input())
    ans[a] = 0
    
for i in range(2,n+1):
    if ans[i]==0:
        continue
    else:
        ans[i] = ans[i-2] + ans[i-1]
print(ans[n]%(10**9+7))

Solution (Python):

N, M = map(int, input().split())

mod = 1000000007;


dp = [0]*(N+1)
broken = [0]*(N+1)


dp[0] = 1
dp[1] = 1


for _ in range(M) :
    broken[int(input())] = -1


for i in range(2, N+1):
        
    if (broken[i-1] != -1):
        dp[i] += dp[i-1]
    
    if (broken[i-2] != -1):
        dp[i] += dp[i-2]
    
    dp[i] %= mod

print(dp[-1])

Solution (Python):
MOD = 10**9 + 7

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
a = [0] * (n + 1)
for _ in range(m):
    a[int(input())] = 1


dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 1 if a[1] == 0 else 0

for i in range(2, n+1):
    dp[i] = (dp[i-1] + dp[i-2]) % MOD if a[i] == 0 else 0

print(dp[-1])

Solution (Python):
n, m = map(int, input().split())
dp = [0] * (n+1)
isSafe = [0] * (n+1)
a = [0] * m
for i in range(m):
    isSafe[int(input())] = 1

dp[0] = 1
dp[1] = 1 if isSafe[1] == 0 else 0

for i in range(2, n+1):
    if isSafe[i-2] == 0:
        dp[i] += dp[i-2]
        dp[i] %= 1000000007
    if isSafe[i-1] == 0:
        dp[i] += dp[i-1]
        dp[i] %= 1000000007

print(dp[len(dp)-1])

Solution (Python):
n,m=map(int,input().split())
a=set([int(input()) for i in range(m)])
dp=[0]*(n+1)
dp[0]=1
for i in range(1,n+1):
    dp[i]=(dp[i-1]+dp[i-2])%(10**9+7)
    if i in a:dp[i]=0
print(dp[n])

Solution (Python):
N, M = map(int, input().split())
BrokenSteps = [int(input()) for _ in range(M)]
 
MOD = 1000000007
 

dp = [0]*(N+1)
dp[0] = 1
if 1 not in BrokenSteps:  
    dp[1] = 1

steps = list(range(2, N+1))  
NoBrokenSteps = list(set(steps) - set(BrokenSteps))
    
for i in NoBrokenSteps:
    dp[i] = (dp[i - 1] + dp[i - 2]) % MOD
        
print(dp[-1])

Solution (Python):
N, M = map(int, input().split())
DP = [0]*(N+2)
DP[0] = 1
A = []
for i in range(M):
    a = int(input())
    DP[a] = -1

mod = 1000000007



for i in range(N):
    if DP[i] == -1:
        continue
    if DP[i + 1] != -1:
        DP[i + 1] = (DP[i] + DP[i + 1]) % mod
    if DP[i + 2] != -1:
        DP[i + 2] = (DP[i] + DP[i + 2]) % mod
print(DP[N])

Solution (Python):
n,m = map(int,input().split())
oks = [True]*(n+1)
for i in range(m):
    a = int(input())
    oks[a] = False
dp = [0]*(n+1)
dp[0] = 1
for i in range(n+1):
    for j in range(i+1,min(n+1,i+3)):
        if oks[j]:
            dp[j] += dp[i]
            dp[j] %= 1000000007
print(dp[n])

Solution (Python):
n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]
mod = int(1e9 + 7)
notbroken = [True for _ in range(n+1)]

for i in a:
  notbroken[i] = False

dp = [0 for _ in range(n+1)]
dp[0] = 1
if notbroken[1]: dp[1] = 1

for i in range(2, n+1):
    if notbroken[i]:
        dp[i] += dp[i-1] + dp[i-2]
        dp[i] %= mod

print(dp[n])

Solution (Python):
n, m = [int(i) for i in input().split(" ")]

l = list(range(1, n+1))
divider = 10**9 + 7
ans = [0]*(n + 1)
broken = [False]*(n+1)
ans[0] = 1
ans[1] = 1

for i in range(m):
    a = int(input())
    broken[a] = True
    if a == 1:
        ans[1] = 0
    
for i in range(2,n+1):
    if broken[i] == False:
        ans[i] = ans[i-1] + ans[i-2]
    
   
print(ans[n] % divider)

Solution (Python):
n,m = map(int, input().split())
a = [True]*(n+1)
for i in range(m):
    t = int(input())
    a[t] = False

x = [0]*(n+1)
x[0] = 1
if a[1]:
    x[1] = 1


for i in range(2, n+1):
    if a[i]:
        x[i] = x[i-1]+ x[i-2]
print(x[n]%1000000007)

Solution (Python):
MOD = 10 ** 9 + 7
n, m = map(int, input().split())
broken = [False] * (n + 1)
for i in range(m):
    a = int(input())
    broken[a] = True
dp = [0] * (n+1)
dp[0] = 1
for i in range(n):
    dp[i] %= MOD
    if broken[i]:
        dp[i] = 0
    if i + 1 <= n:
        dp[i+1] += dp[i]
    if i + 2 <= n:
        dp[i+2] += dp[i]
print(dp[n] % MOD)

Solution (Python):
n, m = map(int, input().split())
a = set()
for i in range(m):
    a.add(int(input()))
dp = [0] * (n+1)
dp[0] = 1
if not(1 in a):
    dp[1] = 1

for i in range(2,n+1):
    if i-1 in a:
        dp[i] = dp[i-2]
        dp[i-1] = 0
    else:
        dp[i] = dp[i-1] + dp[i-2]

print((dp[n])%1000000007)