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.



Sample input:
6 1
3


Sample output:
4

Submission status: Runtime Error

Solution code:
mod = 10**9+7
n,m = map(int,input().split())
a = set([int(input()) for _ 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]) % mod
    if i in a :
        dp[i] = 0

print(dp[n])

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
A = []
for i in range(M):
    A.append(int(input()))
mod = 1000000007
dp=[0]*(N+1)
dp[0]=1
if A[0]!=1:dp[1]=1 
else:dp[1]=0
    
for i in range(2,N+1):
    if i in A:
        dp[i]=0
    else:
        dp[i] = (dp[i-1]+dp[i-2])%mod

print(dp[-1])

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
A = [int(input()) for _ in range(M)]
mod = 1000000007
dp=[0]*(N+1)
dp[0]=1
if A[0]!=1:dp[1]=1 
else:dp[1]=0
    
for i in range(2,N+1):
    if i in A:
        dp[i]=0
    else:
        dp[i] = (dp[i-1]+dp[i-2])%mod

print(dp[-1])

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
A = [int(input()) for _ in range(M)]
mod = 1000000007
dp=[0]*(N+1)
dp[0]=1
if A[0]!=1:dp[1]=1 
else:dp[1]=0
    
for i in range(2,N+1):
    if i in A:
        dp[i]=0
    else:
        dp[i] = (dp[i-1]+dp[i-2])%mod

print(dp[N])

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
l = [int(input()) for _ in range(m)]
q = 10**9+7
memo = [0]*(n+1)
memo[0]=1
def a(x):
  if x in l :
    return 0
  elif x==1:
    memo[1]=1
    return 1
  else:
    if memo[x]!=0:
      return memo[x]
    else:
      memo[x] = a(x-1)+a(x-2)
      return (a(x-1)+a(x-2))
print(a(n)%q)

Submission status: Runtime Error

Solution code:
n,m=list(map(int,input().split(" ")))
a=[]
for i in range(m):
  a.append(int(input()))
dp=[float("inf") for i in range(n)]
dp[0]=0
if 1 in a:
  dp[1]=0
else:
  dp[1]=1
for i in range(2,n):
  if (i-1 not in a)and(i-2 not in a):
    dp[i]=dp[i-1]+dp[i-2]
  elif (i-1 not in a)and(i-2 in a):
    dp[i]=dp[i-1]
  elif (i-1 in a)and(i-2 not in a):
    dp[i]=dp[i-2]
  else:
    dp[i]=0
print(n)

Submission status: Runtime Error

Solution code:
n, m = [int(x) for x in input().split()]
a_list = [0] * m
for i in range(m):
    a_list[i] = int(input())

mod = 1000000007

temp_list = [0] * (n + 1)
temp_list[0] = 1
if a_list[0] != 1:
    temp_list[1] = 1
    j = 0
else:
    j = 1

for i in range(2, n + 1):
    if j < m and i == a_list[j]:
        j += 1
        continue
    temp_list[i] = (temp_list[i - 2] + temp_list[i - 1]) % mod
print(temp_list[n])

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
a = [0]*m
for i in range(m):
    a[i] = int(input())
b=a[0]
for i in range(m-1):
    b = max(b,a[i+1]-a[i])
fib=[0,1]
for i in range(b-1):
    fib.append(fib[i]+fib[i+1])
ans = fib[a[0]]
for i in range(m-1):
    ans *= fib[a[i+1]-a[i]-1]
    ans % 1000000007
    print(ans)
ans *= fib[n-a[m-1]]
print(ans%1000000007)

Submission status: Runtime Error

Solution code:
# coding: utf-8

n, m = map(int, input().split())
z = 10**9 + 7

ans = [1]
a_i = int(input())
m_count = 1
if a_i == 1:
    ans.append(0)
    if m_count < m:
        a_i = int(input())
        m_count += 1
else:
    ans.append(1)
        
for i in range(2, n+1):
    if a_i == i:
        ans.append(0)
        if m_count < m:
            a_i = int(input())
            m_count += 1
    else:
        ans.append(ans[i-1]+ans[i-2])
        
# print(ans, ans[67])
print(int(ans[-1]%z))

Submission status: Runtime Error

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
    
def main():
    n,m=map(int,input().split())
    A=[int(input())for _ in range(m)]
    flag=[True]
    for a in A:
        flag[a]=False
    mod=10**9+7
    dp=[0]*(n+1)
    dp[0]=1
    for i in range(n):
        if flag[i+1]:
            dp[i+1]+=dp[i]%mod
        if flag[i+2] and i<n-1:
            dp[i+2]+=dp[i]%mod
    print(dp[n]%mod)

if __name__=='__main__':
    main()

Submission status: Runtime Error

Solution code:
N,M = map(int, input().split())
arr = [int(input()) for _ in range(0,M)]

arr = [-1]+arr+[N+1]
from math import factorial
count = 0
for i in range(0,len(arr)-1):
    start,end = arr[i],arr[i+1]
    span = end - start - 2 # the first step is taken by a certain step (with no choice)
    if span < 0:
        count = 0 # impossible
        break 
    nptn = int(span/2)
    regional_count = 0

    for k in range(0,nptn+1):
        #regional_count += factorial(span-k) // factorial(k) // factorial(span-2*k)
        mul = lambda a,b: a*b
        regional_count += reduce(mul, range(span-k,k,-1),1) // reduce(mul, range(1,span-2*k+1),1)
    
    if count == 0:
        count += regional_count
    else:
        count *= regional_count
print(count % 1000000007)

Submission status: Runtime Error

Solution code:
N,M = map(int, input().split())
arr = [int(input()) for _ in range(0,M)]

arr = [-1]+arr+[N+1]
from math import factorial
count = 0
for i in range(0,len(arr)-1):
    start,end = arr[i],arr[i+1]
    span = end - start - 2 # the first step is taken by a certain step (with no choice)
    nptn = int(span/2)
    regional_count = 0
    print(span,nptn)
    for k in range(0,nptn+1):
        print(span,k,factorial(span-k)//factorial(k)//factorial(span-2*k))
        regional_count += factorial(span-k) // factorial(k) // factorial(span-2*k)
    print(regional_count)
    if count == 0:
        count += regional_count
    else:
        count *= regional_count
print(count % 1000000007)

Submission status: Runtime Error

Solution code:
def main():
    n,m=map(int,input().split())
    res=[1,1]
    a=int(input())
    gap=[a-1]
    flg=0
    mod=10**9+7
    for i in range(m-1):
        b=int(input())
        dif=b-a-1
        if dif==0:
            flg=1
            break
        else:
            gap.append(dif-1)
            a=b
    if flg==1:
        print(0)
    else:
        gap.append(n-a-1)
        for i in range(2,max(gap)+1):
            res.append((res[i-1]+res[i-2])%mod)
        ans=1
        for i in gap:
            ans=(ans*res[i])%mod
        print(ans)
if __name__=="__main__":
    main()

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
a=[int(input()) for i in range(M)]
MOD=1000000007
DP=[0]*N
DP[0]=1 #1段目にいく方法
DP[1]=1 #２段目に行く方法
for i in range(2,N):
  if i in a:
    DP[i]=0
  else:
    DP[i]=DP[i-1]+DP[i-2]
    DP[i]=DP[i]%MOD
print(DP[N-1])

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
a=list(input())
MOD=1000000007
DP=[0]*N
DP[0]=1 #1段目にいく方法
DP[1]=1 #２段目に行く方法
for i in range(2,N):
  DP[i]=DP[i-1]+DP[i-2]
  DP[a[i]]=0
  DP[i]=DP[i]%MOD
print(DP[N-1-M])

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
a=list(input())
MOD=1000000007
DP=[0]*N
DP[0]=1 #1段目にいく方法
DP[1]=1 #２段目に行く方法
for i in range(2,N):
  DP[i]=DP[i-1]+DP[i-2]
  del DP[a[i]]
  DP[i]=DP[i]%MOD
print(DP[N-1-M])

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
a=list(input())
MOD=1000000007
DP=[0]*N
DP[0]=1 #1段目にいく方法
DP[1]=1 #２段目に行く方法
for i in range(2,N):
  DP[i]=DP[i-1]+DP[i-2]
  del DP[a[i]]
  DP[i]=DP[i]%MOD
print(DP[N-1])

Submission status: Runtime Error

Solution code:
from sys import exit
from collections import deque

n, m = map(int,input().split())
a = deque(int(input()) for i in range(m))

base = a.popleft()
p = 10 ** 9 + 7

dp = [1] * (n+1)

if base == 0:
    print(0)
    exit()

for i in range(1, n+1):
    if base == i:
        dp[i] = 0
        if len(a) != 0:
            base = a.popleft()
        continue
    if i == 1:
        dp[i] = 1
    else:
        dp[i] = (dp[i-2] + dp[i-1]) % p
    if dp[i] == 0:
        print(0)
        exit()

print(dp[n])

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
a=[int(input()) for _ in range(m)]
def fb(num):
    a,b = 1,0
    for _ in range(num+1):
        a,b = a+b,a
    return b
if m=0:
    print(fb(n)%(10**9+7))
    exit()
if m>1:
    for i in range(m-1):
        if a[i+1]-a[i]==1:
            print(0)
            exit()
c=0
for i in range(m):
    if i==0 and a[0]==1:
        c+=1
    elif i==0:
        c+=fb(a[0]-1)
    else:
        c*=(fb(a[i]-a[i-1]-2)%(10**9+7))
c*=fb(n-a[-1]-1)%(10**9+7)
print(c%(10**9+7))

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
a=[int(input()) for _ in range(m)]
def fb(num):
    a,b = 1,0
    for _ in range(num+1):
        a,b = a+b,a
    return b%(10**9+7)
if m=0:
    print(fb(n)%(10**9+7))
    exit()
if m>1:
    for i in range(m-1):
        if a[i+1]-a[i]==1:
            print(0)
            exit()
c=0
for i in range(m):
    if i==0 and a[0]==1:
        c+=1
    elif i==0:
        c+=fb(a[0]-1)
    else:
        c*=(fb(a[i]-a[i-1]-2)%(10**9+7))
c*=fb(n-a[-1]-1)%(10**9+7)
print(c%(10**9+7))

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
a=[int(input()) for _ in range(m)]
if m>1:
    for i in range(m-1):
        if a[i+1]-a[i]==1:
            print(0)
            exit()
def fb(num):
    a,b = 1,0
    for _ in range(num+1):
        a,b = a+b,a
    return b
c=0
for i in range(m):
    if i==0 and a[0]==1:
        c+=1
    elif i==0:
        c+=fb(a[0]-1)
    else:
        c*=(fb(a[i]-a[i-1]-2)%(10**9+7))
c*=fb(n-a[-1]-1)%(10**9+7)
print(c%(10**9+7))

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
a=[int(input()) for _ in range(m)]
if m>1:
    for i in range(m-1):
        if a[i+1]-a[i]==1:
            print(0)
            exit()
def fb(num):
    a,b = 1,0
    for _ in range(num+1):
        a,b = a+b,a
    return b
c=0
for i in range(m):
    if i==0 and a[0]==1:
        c+=1
    elif i==0:
        c+=fb(a[0]-1)
    else:
        c*=(fb(a[i]-a[i-1]-2)%(10**9+7))
    print(c)
c*=fb(n-a[-1]-1)%(10**9+7)
print(c%(10**9+7))

Submission status: Runtime Error

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()
a = [INT()]
for i in range(1, M):
	a.append(INT())
	if a[i] == a[i-1]+1:
		print(0)
		exit()
m = [a[0]-1]
for i in range(1, M):
	m.append(a[i]-a[i-1]-2)
m.append(N-a[M-1]-1)


def Fibo(n):
	S = [1, 1]
	if n == 1:
		return 1
	for i in range(1, n):
		S.append(S[i] + S[i-1])

	return S[n]

ans = 1
for n in m:
	ans *= Fibo(n)

print(ans%mod)

Submission status: Runtime Error

Solution code:
n,m = map(int, input().split())
a = [int(input()) for _ in range(m)]
mod = 1000000007
fib = [1,1,2]
for i in range(3,n+1):
    fib.append((fib[i-2]+fib[i-1])%mod)
ans = 0
ans += fib[a[0]-1]

for i in range(1,m):
    if (a[i]-a[i-1]!=1):
        ans *= fib[a[i]-a[i-1]-2]
        ans %= mod
    else:
        print(0)
        exit()
ans *= fib[n-a[m-1]-1]
print(ans%mod)

Submission status: Runtime Error

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

ans=[]
ans.append(1 if dp[0]==1 else 0)
if dp[0]==1 and dp[1]==1:
    ans.append(2)
elif dp[0]==1 and dp[1]==0:
    ans.append(0)
elif dp[0]==0 and dp[1]==1:
    ans.append(1)
elif dp[0]==0 and dp[1]==0:
    print(0)
    exit()
for i in range(2,n):
    ans.append((ans[i-1]+ans[i-2])*dp[i]%mod)
print(ans[-1]%mod)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
a=[]
for _ in range(m):
    a.append(int(input()))
ans=1
a.sort()
d={0:1,1:1,2:2,3:3,4:5,5:8,6:13}
def func(n):
    if n in d:
        return d[n]
    else:
        v = func(n-1)+func(n-2)%(10**9+7)
        d[n]=v
        return v
ps=-1
a.append(n+1)
for ai in a:
    c=ai-ps-2
    ps=ai
    if c<0:
        print(0)
        exit()
    c=func(c)
    ans*=c
    ans%=10**9+7

print(ans%(10**9+7))

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
a=[]
for _ in range(m):
    a.append(int(input()))
ans=1
a.sort()
def func(n):
    if n<=3:
        return max(1,n)
    else:
        return func(n-1)+func(n-2)
ps=-1
a.append(n+1)
for ai in a:
    c=ai-ps-2
    ps=ai
    if c<0:
        print(0)
        exit()
    c=func(c)
    ans*=c
    ans%=10**9+7

print(ans%(10**9+7))

Submission status: Runtime Error

Solution code:
// Fibonacci 
#include <bits/stdc++.h> 
using namespace std; 
long long dp[1000];
long long MOD {1000000007}; 
int main () {
    ios::sync_with_stdio(false);

    int n; cin >> n; 
    int m; cin >> m; 
    vector<int> broken(100010, 0);
    int x;
    for (int i = 0; i < m; i++) {
        cin >> x; 
        broken[x] = 1; 
    }

    dp[0] = 1;
    for (int num = 0; num < n; num++) {
        for (int next = num+1; next <= min(num+2, n); next++) {
            if (not broken[next]) { 
                dp[next] += dp[num]; 
                dp[next] = dp[next] % 1000000007; 
            }
            else 
                dp[next] = 0;
        }
    }

    // for (int i = 0; i <= n; i++) {
    //     cout << dp[i] << " "; 
    // }
    cout << dp[n]; 
}

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
l = [int(input()) for _ in range(m)]
q = 10**9+7
memo = [-1]*(n+1)
memo[0]=1
for i in l:
  memo[i]=0
def a(x):
  if x in l :
    continue
  elif x==1:
    memo[1]=1
    return 1
  else:
    if memo[x]!=-1:
      return memo[x]
    else:
      memo[x] = a(x-1)+a(x-2)
      return (a(x-1)+a(x-2))
print(a(n)%q)

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
l = [int(input()) for _ in range(m)]
q = 10**9+7
memo = [-1]*(n+1)
memo[0]=1
def a(x):
  if x in l :
    memo[x]=0
    return 0
  elif x==1:
    memo[1]=1
    return 1
  else:
    if memo[x]!=-1:
      return memo[x]
    else:
      memo[x] = a(x-1)+a(x-2)
      return (a(x-1)+a(x-2))%q
print(a(n)%q)

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
l = [int(input()) for _ in range(m)]
q = 10**9+7
memo = [0]*(n+1)
memo[0]=1
def a(x):
  if x in l :
    return 0
  elif x==1:
    memo[1]=1
    return 1
  else:
    if memo[x]!=0:
      return memo[x]
    else:
      memo[x] = a(x-1)+a(x-2)
      return (a(x-1)+a(x-2))%q
print(a(n)%q)

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
l = [int(input()) for _ in range(m)]
q = 10**9+7
memo = [0]*(n+1)
memo[0]=1
def a(x):
  if x in l :
    return 0
  elif x==1:
    memo[1]=1
    return 1
  else:
    if memo[x]!=0:
      return memo[x]
    else:
      memo[x] = a(x-1)+a(x-2)
      return (a(x-1)+a(x-2))%
print(a(n)%q)

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
l = [int(input()) for _ in range(m)]
q = 10**9+7
memo = [0]*(n+1)
memo[0]=1
def a(x):
  if x in l :
    memo[x]=0
    return 0
  elif x==1:
    memo[1]=1
    return 1
  else:
    if memo[x]!=0:
      return memo[x]
    else:
      memo[x] = a(x-1)+a(x-2)
      return (a(x-1)+a(x-2))
print(a(n)%q)

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
l = [int(input()) for _ in range(m)]
q = 10**9+7
memo = [0]*(n)
def a(x):
  if x in l :
    return 0
  if x==1:
    return 1
  elif x==2 and ( 1 in l):
    return 1
  elif x ==2:
    return 2
  else:
    if memo[x-1]!=0:
      return memo[x-1]
    else:
      memo[x-1] = a(x-1)+a(x-2)
      return (a(x-1)+a(x-2))
print(a(n)%q)

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
l = [int(input()) for _ in range(m)]
q = 10**9+7

def a(x):
  memo = [0]*(x)
  if x in l :
    return 0
  if x==1:
    return 1
  elif x==2:
    return 2
  else:
    if memo[x-1]!=0:
      return memo[x-1]
    else:
      memo[x-1] = a(x-1)+a(x-2)
      return (a(x-1)+a(x-2))%q
print(a(n)%q)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100000)

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

mod = 1000000007
  
ans = 1
result = {0:1, 1:1}

def fib(x):
    if(result.get(x)):
        return result.get(x)
    
    if x == 0 or x == 1:
        return result[x]
    else:
        a = fib(x - 1)
        result[x-1] = a
        b = result.get(x-2)
        
        return a + b

x = 0

for a in a_list:
    if a == x:
        ans = 0
        break
    
    ans = (ans * fib((a-1)-x)) % mod
    x = a+1
else:
    ans = (ans * fib(N-x)) % mod

print(ans)

Submission status: Runtime Error

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

mod = 1000000007
  
ans = 1
result = {0:1, 1:1}

def fib(x):
    if x == 0 or x == 1:
        return result[x]
    else:
        a = result.get(x-1) if result.get(x-1) else fib(x - 1)
        result[x-1] = a
        b = result.get(x-2)
        
        return a + b

x = 0

for a in a_list:
    if a == x:
        ans = 0
        break
    
    ans = (ans * fib((a-1)-x)) % mod
    x = a+1
else:
    ans = (ans * fib(N-x)) % mod

print(ans)

Submission status: Runtime Error

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

mod = 1000000007
  
ans = 1

def fib(x):
    if x == 0 or x == 1:
        return 1
    else:
        return (fib(x - 1) + fib(x - 2))

x = 0

for a in a_list:
    if a == x:
        ans = 0
        break
    
    ans = (ans * fib((a-1)-x)) % mod
    x = a+1
else:
    ans = (ans * fib(N-x)) % mod

print(ans)

Submission status: Runtime Error

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

T = 1
for i in range(M-1):
    if a[i]+1==a[i+1]:
        T = 0
        break
if T == 0:
    print(0)
else:
    if N==1:
        print(1)
    elif N == 2:
        print(2)
    else:
        L = [0 for _ in range(N)]
        if 0 in a:
            L[0] = 0
            L[1] = 1 
        else:
            L[0] = 1
            if 1 in a:
                L[1] = 0
            else:
                L[1] = 2
        for i in range(2,N):
            S = i-2 in a
            T = i-1 in a
            U = i in a
            if U:
                L[i] = 0
            elif T:
                L[i] = L[i-2]%1000000007
            else:
                if S:
                    L[i] = L[i-1]%1000000007
                else:
                    L[i] = (L[i-1]+L[i-2])%1000000007
    print(L[-1])

Submission status: Runtime Error

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

#dp[i]:i段目までの上がり方

div = 1000000007

dp = [0] * (N+1)
dp[0] = 1
if not 1 in a:
    dp[1] = 1
else:
    del a[0]

def stairs():
    for i in range(N-1):
        if dp[i+1] == 0 and dp[i] == 0:
            break
        if i+2 != a[0]:
            del a[0]
        else:
            dp[i+2] = (dp[i+1] + dp[i]) % div
    print(dp[N])

stairs()

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
dp = [0]*n

for i in range(m):
    dp[int(input())-1] = 10**12
    
if dp[0] == 10**12:
    dp[0] = 0
else:
    dp[0] = 1

if dp[1] == 10**12:
    dp[1] = 0
else:
    dp[1] = 1+ dp[0]

mod = 1000000007

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

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
dp = [0]*n

for i in range(m):
    dp[int(input())-1] = 10**12
    
if dp[0] == 10**12:
    dp[0] = 0
else:
    dp[0] = 1

if dp[1] == 10**12:
    dp[1] = 0
else:
    dp[1] = 1+ dp[0]

mod = 1000000007

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

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
a_list = []
for i in range(m):
    a_list.append(int(input()))
    
mod = 1000000007

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

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
a_list = []
for i in range(m):
    a_list.append(int(input()))
    
mod = 1000000007

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

Submission status: Runtime Error

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

dp = [0] * (n+1)
dp[0] = 1
dp[1] = 1 if 1 not in a_ls else 0
for i in range(n):
    if i + 2 not in a_ls and i not in a_ls and i+1 not in a_ls:
        dp[i+2] = dp[i] + dp[i+1] 
    elif dp[i+2] in a_ls:
        dp[i+2] = 0
    elif i in a_ls and i+1 not in a_ls:
        dp[i+2] = dp[i+1]
    elif i not in a_ls and i+1 in a_ls:
        dp[i+2] = dp[i]
print(dp[-1] % 1000000007)

Submission status: Runtime Error

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

large = 10**9 +7
count = [0]*(n+1)
itr = 0
count[0] = 1
if a[0] != 1 :
    count[1] = 1
else:
    count[1] = 0
    itr = 1

for i in range(2,n+1):
    if itr<len(a) and a[itr] == i:
        itr +=1
        continue
    else:
        count[i] = (count[i-1] + count[i-2])%large

print(count[n])

Submission status: Runtime Error

Solution code:
N, M=map(int, input().split())
mod=10**9+7
pre=-1
hole=[]
for i in range(M):
  a=int(input())
  hole.append(a-1-pre)
  pre=a
hole.append(N-pre)

  

dp=[0]*(N+1)
dp[1]=1
dp[2]=1
for i in range(3,N+1):
  dp[i]=(dp[i-1]+dp[i-2])%mod
if len(hole)==1:
  print(dp[N])
  
#print(dp)
#print(hole)
ans=1
for h in hole:
  ans*=dp[h]
  ans%=mod
  
print(ans)

Submission status: Runtime Error

Solution code:
N, M=map(int, input().split())
mod=10**9+7
pre=-1
hole=[]
for i in range(M):
  a=int(input())
  hole.append(a-1-pre)
  pre=a
hole.append(N-pre)

dp=[0]*(N+1)
dp[1]=1
dp[2]=1
for i in range(3,N+1):
  dp[i]=(dp[i-1]+dp[i-2])%mod
  
#print(dp)
#print(hole)
ans=1
for h in hole:
  ans*=dp[h]
  ans%=mod
  
print(ans)

Submission status: Runtime Error

Solution code:
import sys
n, m = map(int, input().split())
danger = [int(input()) for i in range(m)]

MOD = 1000000007
MAX = 1000000           #適当な数を入力
fac, finv, inv = [[0]*MAX for i in range(3)]
def combinit():     #MAXまでの下準備
  fac[0] = fac[1] = 1
  finv[0] = finv[1] = 1
  inv[1] = 1
  for i in range(2, MAX):
    fac[i] = fac[i - 1] * i % MOD
    inv[i] = MOD - inv[MOD%i] * (MOD // i) % MOD
    finv[i] = finv[i - 1] * inv[i] % MOD

def modcomb(n, k):      #mod(nCk)を計算、ただしn<MAX
  if (n < k):
    return 0
  if (n < 0 or k < 0):
    return 0
  return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD
combinit()          #下準備の実行 O(MAX)

def poss(n):
  n -= 1
  k = n//2
  ans = 0
  for i in range(k+1):
    ans += modcomb(n-i, i) % MOD
  return ans % MOD

ans = poss(danger[0])
for i in range(1, m):
  if danger[i] - danger[i-1] == 1:
    print(0)
    sys.exit()
  ans *= poss(danger[i] - danger[i-1] - 1)
  ans = ans % MOD
ans *= poss(n - danger[m-1])

print(ans % MOD)

Submission status: Runtime Error

Solution code:
from functools import lru_cache

def main():
    n,m = map(int,input().split())
    A = []
    for _ in range(m):
        a = int(input())
        A.append(a)
    mod = 10**9+7
    @lru_cache(maxsize=1000000)
    def root(n):
        if n==0:
            return 1
        if n==1:
            if 1 in A:
                return 0
            else:
                return 1
        else:
            if n-1 in A and n-2 in A:
                return 0
            elif n-1 in A and n-2 not in A:
                return root(n-2)%mod
            elif n-1 not in A and n-2 in A:
                return root(n-1)%mod
            else:
                return (root(n-1)+root(n-2))%mod
    print(root(n))

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from functools import lru_cache

def main():
    n,m = map(int,input().split())
    A = []
    for _ in range(m):
        a = int(input())
        A.append(a)
    mod = 10**9+7
    @lru_cache(maxsize=1000000)
    def root(n):
        if n==0 or n==1:
            return 1
        else:
            if n-1 in A and n-2 in A:
                return 0
            elif n-1 in A and n-2 not in A:
                return root(n-2)%mod
            elif n-1 not in A and n-2 in A:
                return root(n-1)%mod
            else:
                return (root(n-1)+root(n-2))%mod
    print(root(n))

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
def main():
    n,m = map(int,input().split())
    A = []
    for _ in range(m):
        a = int(input())
        A.append(a)
    mod = 10**9+7
    def root(n):
        if n==0 or n==1:
            return 1
        else:
            if n-1 in A and n-2 in A:
                return 0
            elif n-1 in A and n-2 not in A:
                return pow(root(n-2),1,mod)
            elif n-1 not in A and n-2 in A:
                return pow(root(n-1),1,mod)
            else:
                return pow(root(n-1)+root(n-2),1,mod)
    print(root(n))

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from functools import lru_cache

def main():
    n,m = map(int,input().split())
    A = []
    for _ in range(m):
        a = int(input())
        A.append(a)
    mod = 10**9+7
    @lru_cache(maxsize=100000)
    def root(n):
        if n==0 or n==1:
            return 1
        else:
            if n-1 in A and n-2 in A:
                return 0
            elif n-1 in A and n-2 not in A:
                return pow(root(n-2),1,mod)
            elif n-1 not in A and n-2 in A:
                return pow(root(n-1),1,mod)
            else:
                return pow(root(n-1)+root(n-2),1,mod)
    print(root(n))

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from functools import lru_cache

def main():
    n,m = map(int,input().split())
    A = []
    for _ in range(m):
        a = int(input())
        A.append(a)
    mod = 10**9+7
    @lru_cache(maxsize=1000)
    def root(n):
        if n==0 or n==1:
            return 1
        else:
            if n-1 in A and n-2 in A:
                return 0
            elif n-1 in A and n-2 not in A:
                return pow(root(n-2),1,mod)
            elif n-1 not in A and n-2 in A:
                return pow(root(n-1),1,mod)
            else:
                return pow(root(n-1)+root(n-2),1,mod)
    print(root(n))

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
def fib(n, broken):
    a = 1
    b = 1
    for i in range(n-2):
        # if i in broken:

        a, b = b, a + b
    print(b)


t = int(input())
for _ in range(t):
    n, m = [int(x) for x in input().split()]
    broken = set()
    for _ in range(m):
        broken.add(int(input()))

    x = 0
    y = 1
    i = 1
    impossible = False
    while i <= n:
        # print(f'degrau: {i}')
        c = 0
        if i in broken:
            if i + 1 in broken:
                impossible = True
            # print('broken')
            x = y
            # y = x
            # print(f'x: {x}, y: {y}')
            previous_broken = False
            while c < 2:
                i += 1
                if i in broken:
                    if previous_broken:
                        impossible = True
                    previous_broken = True
                    continue
                else:
                    previous_broken = False
                    c += 1
            # i += 2
        else:
            y, x = x + y % 1000000007, y % 1000000007
            # print(f'x: {x}, y: {y}')
        i += 1
    print(0) if impossible else print(y % 1000000007)

Submission status: Runtime Error

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

f = [0] * (n + 1)

f[0] = 1

if a[0] == 1:
    f[1] = 0
else:
    f[1] = 1

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

print(f[n] % 1000000007)

Submission status: Runtime Error

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

a = [0] * m

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

div = 10 ** 9 + 7
f = [0] * n

f[0] = 1
f[1] = 2

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

print(f[n - 1])

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
H = []
for i in range(M):
  H.append(int(input()))

dp = [0]*N # 初期条件
dp[0] = 1
dp[1] = 0 if 1 in H else 1
for i in range(2,N):
      if i in H:
        dp[i] = 0
      else:
        dp[i] = (dp[i-1]+dp[i-2])%1000000007

print(dp[N-1])

Submission status: Runtime Error

Solution code:
import functools
import operator

n,m= map(int,input().split())
li=[int(input()) for i in range(m)]
l=len(li)
a=0
b=0
c=[]
for i in range(l):
  b=li[i]-1
  c.append(b-a)
  a=li[i]+1
c.append(n-(li[-1]+1))
c2=[i for i in c if i<0]
if sum(c2)<0:
  print(0)
else:
  def fib(n):
    x,y=1,2
    if n==1 or n==0:
      return x
    elif n==2:
      return y
    else:
      for i in range(n-2):
        x, y = y,x+y
      return y
  ans=list(map(fib,c))

  result = functools.reduce(operator.mul, ans)
  print(result%1000000007)

Submission status: Runtime Error

Solution code:
MOD = 10**9 + 7
N, M = map(int, input().split())
stairs = [0]*(N+1)
for _ in range(M):
    stairs[int(input())] = 1
ans = [0]*(N+1)
ans[1] = 1 if stairs[1] == 0 else 0
ans[2] = 1 + ans[1] if stairs[2] == 0 else ans[1]
for i in range(3,N+1):
    if stairs[i] == 1:
        ans[i] = 0
        continue
    ans[i] = (ans[i-1] + ans[i-2]) % MOD
print(ans[N])