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,_,*l=map(int,open(0).read().split())
s=set(l)
p,t=0,1
for i in range(n): p,t=t,(p+t)%(10**9+7)*(not{i+1}&s)
print(t)

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

Solution (Python):
def m():
    MOD = 10 ** 9 + 7
    N, M = map(int, input().split())
    A = [int(input()) for _ in range(M)]
    dp = [0] * (N + 1)
    for a in A: dp[a] = -1
    if N == 1:
        if dp[1] != -1:
            return 1
        else:
            return 0
    if dp[1] != -1 and dp[2] != -1:
        dp[1] = 1
        dp[2] = 2
    elif dp[1] != -1 and dp[2] == -1:
        dp[1] = 1
    elif dp[1] == -1 and dp[2] != -1:
        dp[2] = 1
    else:
        return 0

    for i in range(3, N + 1):
        if dp[i] == -1:
            continue
        l = dp[i - 2] if dp[i - 2] != -1 else 0
        r = dp[i - 1] if dp[i - 1] != -1 else 0
        dp[i] = (l + r) % MOD
    return dp[N] % MOD


print(m())

Solution (Python):
n,m = map(int,input().split())
cnt=[]
l=[int(input()) for _ in range(m)]
for i in range(n+1):
    cnt.append(-1)
for i in range(m):
    cnt[l[i]]=0
cnt[0]=1
for i in range(1,n+1):
    if cnt[i]==0:
        continue
    else:
        cnt[i]=cnt[i-1]
        if i>1:
            cnt[i]+=cnt[i-2]

print(cnt[n]%1000000007)

Solution (Python):
mod=10**9+7
n,m=map(int,input().split())
a=[int(input())for _ in range(m)]
a.append(n+1)
fib=[1,1]
for i in range(n):
	r=fib[-1]+fib[-2]
	fib.append(r%mod)
ans=1
now=0
for x in a:
	ans*=fib[x-1-now]
	if x-1-now<0:
		print(0)
		exit()
	ans%=mod
	now=x+1
print(ans)

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

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

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

Solution (Python):
N, M = map(int, input().split())
st = [1 for _ in range(N+1)]
for _ in range(M):
    st[int(input())] = 0
dp = [0 for _ in range(N+1)]
MOD = int(1e9) + 7
dp[0] = 1

if st[1]:
    dp[1] = 1
for i in range(2, N+1):
    if st[i]:
        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)]
MOD = int(1e9) + 7

stair = [True] * N
for i in a:
    stair[i-1] = False


dp = [0] * N
if stair[0]:
    dp[0] = 1
if N >= 2:
    if stair[1]:
        dp[1] = dp[0] + 1
    else:
        dp[1] = 0

for i in range(2, N):
    if not stair[i]:
        dp[i] = 0
        continue
    if stair[i-1] and stair[i-2]:
        dp[i] = (dp[i-1] + dp[i-2])%MOD
    elif stair[i-1]:
        dp[i] = dp[i-1]
    elif stair[i-2]:
        dp[i] = dp[i-2]

print(dp[N-1])

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

Flag = [True for _ in range(N+1)]
for a in A:
    Flag[a] = False

Dp = [0 for _ in range(N+1)]

Dp[0] = 1
if 1 not in A:
    Dp[1] = 1
for i in range(N-1):
    if Flag[i+2]:
        Dp[i+2] = (Dp[i] + Dp[i+1])%(10**9+7)
print(Dp[-1])

Solution (Python):


























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

Solution (Python):
mod = 10**9 + 7
n, m = map(int, input().split())
a = []
for _ in range(m):
    x = int(input())
    if len(a) > 0 and x == a[-1] + 1:
        print(0)
        exit()
    a.append(x)
j = 0
dp = [0] * (n+1)
dp[0] = 1
for i in range(n):
    if j < m and i >= a[j]:
        j += 1
    if j < m and i+1 == a[j]:
        pass
    else:
        dp[i+1] += dp[i]
        dp[i+1] %= mod
    if j < m and i+2 == a[j]:
        pass
    elif i+2 <= n:
        dp[i+2] += dp[i]
        dp[i+2] %= mod
print(dp[-1])

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

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

mod = 10**9+7
dp =[0]*(n+1)
dp[0] =1
for i in range(n):
    dp[i] %= mod
    if (lis[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([int(input()) for _ in range(m)])

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

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

Solution (Python):
n, m = map(int, input().split())
stairs = [1]*(n+1)
for _ in range(m):
  stairs[int(input())] = -1

flg = False
for i in range(2,n+1):
  if stairs[i]==-1:
    pass
  elif stairs[i-1]==-1 and stairs[i-2]==-1:
    flg=True
    break
  elif stairs[i-1]==-1:
    stairs[i] = stairs[i-2]
  elif stairs[i-2]==-1:
    stairs[i] = stairs[i-1]
  else:
    stairs[i] = stairs[i-1] + stairs[i-2]
if flg:
  print(0)
else:
  print(stairs[-1]%1000000007)

Solution (Python):
n,m=map(int,input().split())
a=[1]*(n+1)
flg=0
for i in range(m):
  a[int(input())]=-1
for i in range(2,n+1):
  if a[i]==-1:
    pass
  elif a[i-1]==-1 and a[i-2]==-1:
    flg=1
    break
  elif a[i-1]==-1:
    a[i]=a[i-2]
  elif a[i-2]==-1:
    a[i]=a[i-1]
  else:
    a[i]=a[i-1]+a[i-2]
if flg==1:
  print(0)
else:
  print(a[-1]%1000000007)

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

for i in range(m):
    a = int(input())
    broken[a] = 1

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

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

print(dp[n])

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

DP = [0] * (n + 1)
DP[0] = 1
for i in range(n):
    if not denger[i + 1]:
        DP[i + 1] += DP[i]
    if i + 2 <= n and not denger[i + 2]:
        DP[i + 2] += DP[i]

print(DP[-1] % 1000000007)

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

Solution (Python):
def Fib(n):
    a, b = 0, 1
    if n == 1:
        return a
    elif n == 2:
        return b
    else:
        for i in range(n-2):
            a, b = b, a + b
        return b
n, m = map(int, input().split())
broken = []
for i in range(m):
  broken.append(int(input()))
L = -1
intv = []
for i in broken:
  intv.append(i - L - 2)
  L = i
intv.append(n - L - 1)
res = 1

if -1 in intv[1:]:
  print(0)
  exit()
dv = 10 ** 9 + 7
for i in intv:
  res *= Fib(i + 2)
  res %= dv
print(res)

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

route=[0]*3+[0]*max(0,N-2)
for a in A:
    route[a]=-1

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

if route[2]!=-1:
    route[2]=1+route[1]
else:
    route[2]=0

i=3
while i<=N:
    if route[i]==-1:
        route[i]=0
    else:
        route[i]=(route[i-1]+route[i-2])%1000000007
    i+=1

print(route[N])

Solution (Python):
import sys
n, m = map(int, input().split())
A = [int(input()) for _ in range(m)]
mod = 1000000007

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

B = ['.'] * (n + 1)
for a in A:
    B[a] = '
    
dp = [0] * (n + 1)
if B[1] == '.' and B[2] == '.':
    dp[1] = 1
    dp[2] = 2
elif B[1] == '
    dp[2] = 1
elif B[1] == '.' and B[2] == '
    dp[1] = 1
    
for i in range(3, n + 1):
    if B[i] == '.':
        dp[i] = (dp[i - 2] + dp[i - 1]) % mod
    
print(dp[-1])

Solution (Python):
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
a = [0]*m

 
a = set([int(input()) for i in range(m)])
dp = [0]*(n+1)
dp[0] = 1
if 1 in a:
  dp[1] = 0
else:
  dp[1] = 1

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

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 7)

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


def solve():

    
    if M >= 1:
        temp = A[0]
        for a in A[1:]:
            if a - 1 == temp:
                return 0
            temp = a

    
    memo = [0] * (N + 2)

    def rec(i):
        if i == 0:
            return 1
        if i < 0:
            return 0
        if isBroken[i]:
            return 0

        if memo[i] == 0:
            count1 = rec(i - 1)
            count2 = rec(i - 2)
            memo[i] = (count1 + count2) % 1000000007
        return memo[i]
    return rec(N)


print(solve())

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 7)

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


def solve():

    
    if M >= 1:
        temp = A[0]
        for a in A[1:]:
            if a - 1 == temp:
                return 0
            temp = a

    
    memo = [0] * (N + 2)

    def rec(i):
        if i == 0:
            return 1
        if i < 0:
            return 0
        if isBroken[i]:
            return 0

        if memo[i] == 0:
            count1 = rec(i - 1) % 1000000007
            count2 = rec(i - 2) % 1000000007
            memo[i] = (count1 + count2) % 1000000007
        return memo[i]
    return rec(N)


print(solve())

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

dp = [0]*(N+1)
for j in a:
  dp[j]=-1

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

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

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

Solution (Python):

N, M = map(int, input().split())
A = set(int(input()) for _ in range(M))

m = 1000000007

t = [0] * (N + 2)
t[0] = 1
for i in range(N):
    if i in A:
        t[i] = 0
    else:
        t[i + 1] = (t[i + 1] + t[i]) % m
        t[i + 2] = (t[i + 2] + t[i]) % m
print(t[N])

Solution (Python):
mod = 10**9 + 7
N, M = map(int, input().split())
state = [True]*(N+1)
ans = [0]*(N+1)
for _ in range(M):
    state[int(input())] = False

ans[0] = 1
for i in range(N):
    if state[i]:
        ans[i+1] += ans[i]
        if i < N-1:
            ans[i+2] += ans[i]
print(ans[-1]%mod)

Solution (Python):
import sys
input = sys.stdin.readline

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):
    for j in range(i+1,min(n,i+2)+1):
        if oks[j]:
            dp[j] += dp[i]
            dp[j] %= (10**9+7)
print(dp[n])

Solution (Python):
import sys

N, M = [int(n) for n in input().split()]

A = []

modulus = 10**9 + 7

for _ in range(M):
    a = int(input())
    if A and A[-1] + 1 == a:
        print(0)
        sys.exit(0)
    A.append(a)

fib_list = [1, 1]

def fib_mod(n):
    l = len(fib_list)
    if n < l:
        return fib_list[n]
    while l <= n:
        fib_list.append((fib_list[-1] + fib_list[-2]) % modulus)
        l += 1
    return fib_list[-1]

total = 1
left = 0

A.append(N+1)

for a in A:
    right = a - 1
    total *= (fib_mod(right - left) % modulus)
    left = right + 2


print(total % modulus)

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

MOD = 10**9+7

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

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

print(step[-1])

Solution (Python):

n,m=[int(x) for x in input().rstrip().split()]
A=[int(input()) for i in range(m)]
mod=10**9+7
dp=[0 for i in range(n+10)]
no=[True for i in range(n+10)]
for i in A:
  no[i]=False


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

print(dp[n]%mod)

Solution (Python):
import sys
sys.setrecursionlimit(10**6)

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

MOD = 10**9+7

ok = set([i+1 for i in range(n)]) - set(a)
ok = list(ok)
ok.sort()

MAX_N = 10**5+5
dp = [0]*MAX_N

for i in ok:
    if i == 1:
        dp[i] = 1
    elif i == 2 and dp[1] == 0:
        dp[i] = 1
    elif i == 2:
        dp[i] = 2
    else:
        dp[i] = dp[i-2] + dp[i-1]
        dp[i] %= MOD
        
print(dp[n])

Solution (Python):
N,M=map(int,input().split())
a=[int(input()) for _ in range(M)]
m=10**9+7
a.append(N+1)
def mul(a,b):
    c=[[0]*len(b[0])for i in range(len(a))]
    for i in range(len(a)):
        for k in range(len(b)):
            for j in range(len(b[0])):
                c[i][j]=(c[i][j]+a[i][k]*b[k][j])%m
    return c
def pow(a,n):
    b=[[0]*len(a) for i in range(len(a))]
    for i in range(len(a)):
        b[i][i]=1
    while 0<n:
        if n&1==1:
            b=mul(a,b)
        a=mul(a,a)
        n=n>>1
    return b                
if M==0:
  A=[[1,1],[1,0]]
  print(pow(A,N+1)[1][0])
elif M==1:
  A=[[1,1],[1,0]]
  print((pow(A,a[0])[1][0]*pow(A,N-a[0])[1][0])%m)
else:
  ans=1
  for i in range(M+1):
    A=[[1,1],[1,0]]
    if a[i]+1==a[i-1]:
      ans=0
      break
    if i==0:
      if a[i]!=1:
        ans=ans*pow(A,a[0])[1][0]
        ans=ans%m
    elif i==M:
      ans=ans*pow(A,a[i]-a[i-1]-1)[1][0]
      ans=ans%m
    else:
      ans=ans*pow(A,a[i]-a[i-1]-1)[1][0]
      ans=ans%m
  print(ans)

Solution (Python):

N, M = map(int, input().split())
A = set({})
MAX = 1000000007
for i in range(M):
    a = int(input())
    A.add(a)
dp = [0] * (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-2] + dp[i-1])%MAX
print(dp[N])

Solution (Python):

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

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

dp = [0] * (N+1)
dp[0] = 1
for now in range(N):
    for next in range(now+1, min(N, now+2)+1):
        if oks[next]:
            dp[next] += dp[now]
            dp[next] %= MOD
            
print(dp[N])

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

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


for i in range(A):
    dp[arr[i]]=-1

if dp[1]==-1:
    ans[1]=0

for i in range(2,N+1):
    if dp[i]!=-1:
        ans.append(ans[i-1]+ans[i-2])
    elif dp[i]==-1:
        ans.append(0)
    
print(ans[-1]%1000000007)

Solution (Python):

n,m=map(int,input().split())




dp=[0]*(n+1)
mod=10**9+7
broken={i:False for i in range(1,n+1)}
for i in range(m):
    a=int(input())
    broken[a]=True
if broken[1]:
    dp[1]=0
else:
    dp[1]=1
dp[0]=1
for i in range(2,n+1):
    if not broken[i]:
        dp[i]=(dp[i-1]+dp[i-2])%mod

print(dp[n])

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

l = [0]*(N+1)
l[0] = 1
j = 0
for i in range(1, N+1):
  if j < M and i == a[j]:
    j += 1
  else:
    if i == 1:
      l[1] = 1
    else:
      l[i] = (l[i-1] + l[i-2]) % (10**9+7)

print(l[N])

Solution (Python):
import sys
n,m = map(int,input().split())
ls = set(int(input()) for _ in range(m))
dp = [0]*(n+1)
dp[0] = 1
for i in range(1,n+1):
    if i not in ls:
        dp[i] = (dp[i-1]+dp[i-2])
        if dp[i] >= 10**9+7:
            dp[i] %= 10**9+7 
    else:
        if i-1 in ls:
            print(0)
            sys.exit()
print(dp[-1])

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

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

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

Solution (Python):
N,M = map(int, input().split())
mod = 1000000007
dp = [1 for _ in range(N+1)]
for i in range(M):
	dp[int(input())] = 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):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():

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

    dp = [0] * (N + 10)
    dp[0] = 1
    for i in range(N):
        if B[i]:
            continue
        dp[i + 1] = (dp[i + 1] + dp[i]) % MOD
        dp[i + 2] = (dp[i + 2] + dp[i]) % MOD

    print(dp[N])
    return


if __name__ == '__main__':
    main()

Solution (Python):
N, M = map(int,input().split())
TF = [True]*(N+1)
for m in range(M):
  TF[int(input())] = False
dp = [0]*(N+1)
dp[0]=1
for n in range(N):
  if TF[n] and n<N:
    dp[n+1]+=dp[n]
  if TF[n] and n<N-1:
    dp[n+2]+=dp[n]
print(dp[N]%1000000007)

Solution (Python):

import sys

MOD = 1000000007  


def solve(N: int, M: int, a: "List[int]"):
    a = set(a)
    dp = [0] * (N+2)
    dp[0] = 1
    for i in range(N):
        if i in a:
            dp[i] = 0
        dp[i+1] = (dp[i+1] + dp[i]) % MOD
        dp[i+2] = (dp[i+2] + dp[i]) % MOD
    return dp[N]



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    M = int(next(tokens))  
    a = [int(next(tokens)) for _ in range(M)]  
    print(solve(N, M, a))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    
    main()

Solution (Python):
n,m=map(int,input().split())
a=[]
for i in range(m):
  a_=int(input())
  a.append(a_)
  
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]==-1:
    dp[i]=dp[i-1]+dp[i-2]

print(dp[n]%(1000000007))

Solution (Python):





N,M = map(int,input().split())
MOD = 1000000007
issafe = [True]*(N+1) 

for _ in range(M):
    i = int(input())
    issafe[i] = False 


dp = [0]*(N+1)


dp[0] = 1
if issafe[1]:dp[1] = 1


for n in range(2,N+1):
    if issafe[n-1]: dp[n] += dp[n-1]
    if issafe[n-2]: dp[n] += dp[n-2]
    dp[n] %= MOD

print(dp[N])

Solution (Python):

n,m  = map(int,input().split())
ln = [-1 for i in range(n +1)]
mod_1 = 10**9 + 7
for i in range(m):
    ln[int(input())] = 0

for i in range(n+1):
    if ln[i] ==0:
        pass
    elif i == 0:
        ln[i] = 1
    elif i == 1:
        ln[i] = 1
    else:
        ln[i] = (ln[i-1] + ln[i-2]) % mod_1

print(ln[-1])

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 6)
n, m =map(int,input().split())
lis={0:1,1:1}
for _ in range(m):
  lis[int(input())]=0 
def saiki(x):
  if x not in lis:
        d=saiki(x-1)+saiki(x-2)
        if d >10**9+7:
          lis[x]= d % (10**9+7)
          return lis[x]
        else:
          lis[x]=d
          return d
  else:
    return lis[x]
      
print(saiki(n))

Solution (Python):
'''
Accepted    　:No
difficult   　: 
ペナルティ　  　:5分
実際の回答時間  :分
WAの回数　     :回
合計時間　　  　:分
解説AC
解法：基本的な動的計画法(DP)
'''
import itertools


def myAnswer(N:int,M:int,A:list) -> int:
   safe_stairs =[True] * (N + 1)
   mod = 10**9 + 7
   for a in A:
      safe_stairs[a] = False

   DP = [0] * (N+1)
   DP[0] = 1
   if safe_stairs[1]:DP[1] = 1

   for n in range(2,N + 1):
      if safe_stairs[n - 1]:
         DP[n] += DP[n - 1]
      if safe_stairs[n - 2]:
         DP[n] += DP[n - 2]
      DP[n] %= mod

   return DP[N]
      



def modelAnswer():
   return
def main():
   N,M = map(int,input().split())
   A = [int(input()) for _ in range(M)]
   print(myAnswer(N,M,A))

if __name__ == '__main__':
   main()

Solution (Python):
'''
Accepted    　:No
difficult   　: 
ペナルティ　  　:5分
実際の回答時間  :分
WAの回数　     :回
合計時間　　  　:分
'''
import itertools


def myAnswer(N:int,M:int,A:list) -> int:
   safe_stairs =[True] * (N + 1)
   mod = 10**9 + 7
   for a in A:
      safe_stairs[a] = False

   DP = [0] * (N+1)
   DP[0] = 1
   if safe_stairs[1]:DP[1] = 1

   for n in range(2,N + 1):
      if safe_stairs[n - 1]:
         DP[n] += DP[n - 1]
      if safe_stairs[n - 2]:
         DP[n] += DP[n - 2]
      DP[n] %= mod

   return DP[N]
      



def modelAnswer():
   return
def main():
   N,M = map(int,input().split())
   A = [int(input()) for _ in range(M)]
   print(myAnswer(N,M,A))

if __name__ == '__main__':
   main()

Solution (Python):
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
mod = 1000000007
a = set(int(input()) for _ in range(m))

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[n]%mod)

Solution (Python):
import sys

def MI():
    return map(int, input().split())

def LI():
    return list(map(int, input().split()))

N, M = MI()
mod = 10**9 + 7
stairs = [1] + [0] * N
safe = [True] * (N + 1)

for _ in range(M):
    a = int(input())
    safe[a] = False

if safe[1]:
    stairs[1] = 1

for i in range(2, N + 1):
    if not safe[i - 1] and not safe[i - 2]:
        print(0)
        sys.exit()
        
    if safe[i - 1]:
        stairs[i] += stairs[i - 1]
    
    if safe[i - 2]:
        stairs[i] += stairs[i - 2]
    
    stairs[i] %= mod

print(stairs[N])

Solution (Python):
n,m = map(int, input().split())
A = [int(input()) for i in range(m)]
if m == 0:
  Fib = [1,2]
  for i in range(2,n):
    Fib.append(Fib[i-2]+Fib[i-1])
  print(Fib[n-1]%1000000007)
  exit()

B = [A[i+1]- A[i] for i in range(m-1)]
B.insert(0,A[0]+1)
B.append(n+1-A[m-1])

M = max(A)

Fib = [0,1]
for i in range(2,M+10):
  Fib.append(Fib[i-2]+Fib[i-1])

ans = 1
for i in range(len(B)):
  ans = (ans * Fib[B[i]-1])%1000000007
  
print(ans)

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

  if A[i] == -1:
  	A[i] = A[i+1] + A[i+2]

print(A[0]%(1000000007))

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

MOD = 10**9+7

dp = [0] * (10**5 + 3)
dp[1] = 0
dp[2] = 1
dp[3] = 2
for i in range(3, len(dp)):
    dp[i] = dp[i-1] + dp[i-2] 

res = 1
bef = -1
if M > 0:
    for a in a_list:
        res *= dp[a-bef]
        res %= MOD
        bef = a
res *= dp[N-bef+1]
res %= MOD

print(res)

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

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

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

    ans = dp[n] % mod
    print(ans)


if __name__ == "__main__":
    main()

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

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

nums = [0]*(N+1)
nums[0] = 1
if 1 not in a:
    nums[1] = 1
for i in range(2, N+1):
    if not i in a:
      nums[i] = nums[i-1] + nums[i-2]

print(nums[N]%(1000000007))

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

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

print(nums[n]%mod)

Solution (Python):
li = list(map(int,input().split()))
n,m=li[0],li[1]
_list=[int(input()) for i in range(m)]
is_safe = [True] * (n+1)
for a in _list:
  is_safe[a] = False
DP=[1, 1] if is_safe[1] == True else [1, 0]
for i in range(n-1):
  if is_safe[i+2] == False:
    DP+= [0]
  else:
    DP += [DP[i] + DP[i+1]]
print(DP[n] % 1000000007 if DP[n] != 0 else 0)

Solution (Python):
MOD = 1000000007

def f_dp(x, a):
    dp = [0] * (x + 1)
    dp[0] = 1
    if 1 not in a:
        dp[1] = 1
    for i in range(2, x + 1):
        if i not in a:
            dp[i] = dp[i - 1] + dp[i -2]
    return dp[n] % MOD

if __name__ == "__main__":
    n, m = map(int, input().split())
    a = set([int(input()) for i in range(m)])

    dp = f_dp(n, a)
    print(dp)

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


def solve(n, m, ax):
    bx = []

    for i in range(n):
        is_broken = ax[i]
        if i == 0:
            if is_broken == 1:
                bx.append(0)
            else:
                bx.append(1)
        elif i == 1:
            if is_broken == 1:
                bx.append(0)
            else:
                bx.append(bx[0]+1)
        elif is_broken == 1:
            bx.append(0)
        else:
            if ax[i-2] == 1 and ax[i-1] == 1:
                bx.append(0)
            elif ax[i-2] == 1 and ax[i-1] == 0:
                bx.append(bx[i-1])
            elif ax[i-2] == 0 and ax[i-1] == 1:
                bx.append(bx[i-2])
            else:
                bx.append(bx[i-2] + bx[i-1])


    return bx[-1] % MOD


if __name__ == '__main__':
    n, m = map(int, input().split())
    ax = [0]*(n)
    for i in range(m):
        ax[int(input())-1] += 1

    print(solve(n, m, ax))

Solution (Python):
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
broken = set([int(input()) for _ in range(m)]) 

def ptn_num(x): 
    dp = [0] * (x+1) 
    if 1 in broken: 
        dp[:2] = 1, 0
    else:
        dp[:2] = 1, 1 

    for i in range(2, x+1):
        if i not in broken: 
            dp[i] = (dp[i-1] + dp[i-2]) % (10**9+7) 
    print(dp[-1])

ptn_num(n)

Solution (Python):
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
broken = set([int(input()) for _ in range(m)]) 

def ptn_num(x): 
    dp = [0] * (x+1) 
    if 1 in broken: 
        dp[:2] = 1, 0
    else:
        dp[:2] = 1, 1 

    for i in range(2, x+1):
        if i not in broken: 
            dp[i] = (dp[i-1] + dp[i-2]) % (10**9+7) 
    print(dp[-1])

ptn_num(n)

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

dp = [0] * (n+1)

dp[:2] = 1, 1 if 1 not in a else 0 

for i in range(2, n+1):
    if i not in a:
        dp[i] = ((dp[i-1] + dp[i-2]) % (10**9+7))

print(dp[-1])

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

dp = [0] * (n+1)

dp[:2] = 1, 1 if 1 not in a else 0 

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

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

Solution (Python):
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
broken = set([int(input()) for _ in range(m)]) 

def ptn_num(x): 
    if x == 1:
        print(1)
    else:
        dp = [0] * (x+1) 
        cnt = 0 
        if 1 in broken: 
            dp[:2] = 1, 0
        else:
            dp[:2] = 1, 1 

        for i in range(2, x+1):
            if i in broken: 
                cnt += 1 
                if cnt == 2: 
                    print(0)
                    exit()
            else: 
                dp[i] = (dp[i-1] + dp[i-2]) % (10**9+7) 
                cnt = 0 
        print(dp[-1])

ptn_num(n)

Solution (Python):
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
broken = set([int(input()) for _ in range(m)]) 


def ptn_num(x): 
    if x == 1:
        print(1)
    else:
        dp = [0] * (x+1) 
        cnt = 0 
        if 1 in broken: 
            dp[:2] = 1, 0
        else:
            dp[:2] = 1, 1 

        for i in range(2, x+1):
            if i in broken: 
                cnt += 1
                if cnt == 2: 
                    print(0)
                    exit()
            else: 
                dp[i] = (dp[i-1] + dp[i-2]) % (10**9+7)
                cnt = 0
        
        print(dp[-1])

ptn_num(n)

Solution (Python):
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
broken_steps = set([int(input()) for _ in range(m)])


def ptn_num(x): 
    if x == 1:
        print(1)
    else:
        dp = [0] * (x+1) 
        cnt = 0
        if 1 in broken_steps: 
            dp[:2] = 1, 0
        else:
            dp[:2] = 1, 1 

        for i in range(2, x+1):
            if i in broken_steps: 
                cnt += 1
                if cnt == 2:
                    print(0)
                    exit()
            else: 
                dp[i] = (dp[i-1] + dp[i-2]) % (10**9+7)
                cnt = 0
        
        print(dp[-1])

ptn_num(n)

Solution (Python):
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
broken_steps = set([int(input()) for _ in range(m)])


def ptn_num(x): 
    if x == 1:
        print(1)
    else:
        dp = [0] * (x+1) 
        cnt = 0
        if 1 in broken_steps: 
            dp[:2] = 1, 0
        else:
            dp[:2] = 1, 1 

        for i in range(2, x+1):
            if i in broken_steps: 
                cnt += 1
                if cnt == 2:
                    print(0)
                    exit()
            else: 
                dp[i] = (dp[i-1] + dp[i-2]) % (10**9+7)
                cnt = 0
        
        print(dp[-1])

ptn_num(n)